Submission #719871

#	Time	Username	Problem	Language	Result	Execution time	Memory
719871		ThegeekKnight16	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1037 ms	206608 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int border = 1e9 + 10;
vector<int> minTmp, qnt, e, d;

int create()
{
    minTmp.push_back(LONG_LONG_MAX);
    qnt.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return qnt.size()-1;
}

void copy(int pos, int novo)
{
    minTmp[novo] = minTmp[pos];
    qnt[novo] = qnt[pos];
    e[novo] = e[pos];
    d[novo] = d[pos];
}

int update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return pos;
    int novo = create();
    copy(pos, novo);
    if (ini == fim)
    {
        qnt[novo]++;
        minTmp[novo] = min(minTmp[novo], val);
        return novo;
    }
    int m = (ini + fim) >> 1;
    if (id <= m) e[novo] = update(e[novo], ini, m, id, val);
    else d[novo] = update(d[novo], m+1, fim, id, val);

    qnt[novo] = qnt[e[novo]] + qnt[d[novo]];
    minTmp[novo] = min(minTmp[e[novo]], minTmp[d[novo]]);
    return novo;
}

pair<int, int> query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return make_pair(0, LONG_LONG_MAX);
    if (pos == 0) return make_pair(0, LONG_LONG_MAX);
    if (p <= ini && fim <= q) return make_pair(qnt[pos], minTmp[pos]);
    int m = (ini + fim) >> 1;
    pair<int, int> respE = query(e[pos], ini,  m , p, q);
    pair<int, int> respD = query(d[pos], m+1, fim, p, q);
    return make_pair(respE.first + respD.first, min(respE.second, respD.second));
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<pair<int, int> > v(N);
    for (auto &[x, y] : v) cin >> x >> y;
    int ans = 0LL;
    // while (v.size() > K) {ans += v.back().first; v.pop_back();}

    // reverse(v.begin(), v.end());
    // v.emplace_back(0, 0);
    // reverse(v.begin(), v.end());

    vector<int> Oper(K);
    for (auto &x : Oper) cin >> x;
    Oper.push_back(-1);
    reverse(Oper.begin(), Oper.end());

    vector<int> Raiz(K+1);
    Raiz[0] = create();
    for (int i = 1; i <= K; i++) Raiz[i] = update(Raiz[i-1], 1, border, Oper[i], i);

    for (auto [x, y] : v)
    {
        int resp = 1;
        if (x > y) {resp--; swap(x, y);}

        auto [qntMeio, minMeio] = query(Raiz[K], 1, border, x, y-1);
        if (qntMeio == 0) minMeio = K;
        else resp = 0;

        if (minMeio == LONG_LONG_MAX) minMeio = K;

        auto [qntMaior, minMaior] = query(Raiz[minMeio], 1, border, y, border);
        resp += qntMaior;

        // cerr << i << " " << qntMeio << " " << minMeio << " " << qntMaior << " " << resp << '\n';

        ans += ((resp % 2) ? x : y);
    }

    cout << ans << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65