Submission #1045164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045164		ArashJafariyan	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	389 ms	88132 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse,sse2,fma")

#define pb push_back
#define ll long long
#define i2 array<int, 2>
#define SZ(x) (int) (x).size()
#define int ll
#define pii pair<int, int>
#define F first
#define S second

int power(int a, int b, int mod) {
    int ret = 1;
    while (b) {
        if (b & 1) {
            ret = ret * a % mod;   
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}

const int N = 2e5 + 8;

int n, k, node[(N * 3) << 2], fen[N];
pii A[N], T[N];
vector<int> all;
unordered_map<int, int> f, g;

void set_val(int i, int v, int x = 1, int l = 0, int r = N * 3) {
    if (r - l == 1) {
        node[x] = max(node[x], v);
        return;
    }
    int m = (l + r) >> 1;
    i < m ? set_val(i, v, x << 1, l, m) : set_val(i, v, x << 1 | 1, m, r);
    node[x] = max(node[x << 1], node[x << 1 | 1]);
}

int get(int l, int r, int x = 1, int lx = 0, int rx = N * 3) {
    if (l >= r) {
        return -1;
    }
    if (l == lx && r == rx) {
        return node[x];
    }
    int m = (lx + rx) >> 1;
    return max(get(l, min(r, m), x << 1, lx, m), get(max(l, m), r, x << 1 | 1, m, rx));
}

void update(int i) {
    for (i++; i < N; i += i & -i) {
        fen[i]++;
    }
}

int get_fen(int i) {
    int ret = 0;
    for (i++; i; i -= i & -i) {
        ret += fen[i];
    }
    return ret;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < ((N * 3) << 2); i++) {
        node[i] = -1;
    }

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> A[i].F >> A[i].S;     
        all.pb(A[i].F);
        all.pb(A[i].S);
    }
    for (int i = 0; i < k; i++) {
        cin >> T[i].F;
        T[i].S = i;
        all.pb(T[i].F);
    }

    sort(all.begin(), all.end());
    int give = 0;
    for (int v : all) {
        if (f.find(v) == f.end()) {
            f[v] = give;
            g[give] = v;
            give++;
        }
    }

    for (int i = 0; i < n; i++) {
        A[i].F = f[A[i].F];
        A[i].S = f[A[i].S];
    }
    for (int i = 0; i < k; i++) {
        T[i].F = f[T[i].F];
    }

    sort(A, A + n, [&](pii x, pii y) {
        return max(x.F, x.S) > max(y.F, y.S);        
    });
    sort(T, T + k, [&](pii x, pii y) {
        return x.F > y.F;
    });

    for (int i = 0; i < k; i++) {
        set_val(T[i].F, T[i].S);
    }

    /* cout << "deBUG: ---------\n";
    for (int i = 0; i < n; i++) {
        cout << A[i].F << ' ' << A[i].S << '\n';
    }
    cout << ".\n";
    for (int i = 0; i < k; i++) {
        cout << T[i].F << ' ' << T[i].S << '\n';
    }
    cout << ".\n";
    cout << get(0, 2);
    cout << "-------------\n"; */

    int pt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        auto [a, b] = A[i];
        while (pt < k && T[pt].F >= max(a, b)) {
            update(T[pt].S);
            pt++;
        }

        int last = get(min(a, b), max(a, b));
        // cout << "debug: " << last << '\n';

        if (last == -1) {
            int t = get_fen(N - 2);
            ans += (t % 2 ? g[b] : g[a]);
        }
        else {
            int t = get_fen(N - 2) - get_fen(last);
            if (a > b) {
                swap(a, b);
            }
            ans += (t % 2 ? g[a] : g[b]);
        }
    }
    cout << ans;

    return 0;
}

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