Submission #1111180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111180		adaawf	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	779 ms	69304 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005], c[200005], res[200005], t[2400005], tt[2400005], dd[600005], z = 0;
map<int, int> m;
vector<pair<int, int>> g[200005];
void update(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t[v] = max(t[v], y);
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
void update2(int v, int tl, int tr, int x) {
    if (tl == tr) {
        tt[v]++;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update2(v * 2, tl, mid, x);
    else update2(v * 2 + 1, mid + 1, tr, x);
    tt[v] = tt[v * 2] + tt[v * 2 + 1];
}
int sum2(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return tt[v];
    }
    int mid = (tl + tr) / 2;
    return sum2(v * 2, tl, mid, l, min(r, mid)) + sum2(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<int> v;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> c[i];
        v.push_back(c[i]);
    }
    sort(v.begin(), v.end());
    for (int w : v) {
        if (!m.count(w)) {
            m[w] = ++z;
            dd[z] = w;
        }
    }
    for (int i = 1; i <= n; i++) a[i] = m[a[i]], b[i] = m[b[i]];
    for (int i = 1; i <= q; i++) {
        c[i] = m[c[i]];
        update(1, 1, z, c[i], i);
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) res[i] = 1;
        else {
            if (a[i] < b[i]) {
                int h = sum(1, 1, z, a[i], b[i] - 1) + 1;
                if (h != 1) {
                    res[i] = 1;
                }
                g[h].push_back({i, b[i]});
            }
            else {
                int h = sum(1, 1, z, b[i], a[i] - 1) + 1;
                g[h].push_back({i, a[i]});
            }
        }
    }
    for (int i = q; i >= 1; i--) {
        update2(1, 1, z, c[i]);
        for (auto w : g[i]) {
            int h = sum2(1, 1, z, w.second, z);
            if (h & 1) res[w.first] ^= 1;
        }
    }
    long long int d = 0;
    for (int i = 1; i <= n; i++) {
        if (res[i] == 0) d += dd[a[i]];
        else d += dd[b[i]];
    }
    cout << d;
}

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