oj.uz

Submission #228178

# Submission time Handle Problem Language Result Execution time Memory
228178 2020-04-30T06:07:24 Z tri Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 149796 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

static const int MAXN = 600100, NODES = 9 * MAXN;
// different definition of lz to nicely implement persistence
// lz is only for children, node which it is on already contains updated value
int lC[NODES], rC[NODES], tr[NODES];
int nx = 0;

inline int cpy(int o) {
    int n = nx++;
    lC[n] = lC[o], rC[n] = rC[o], tr[n] = tr[o];
    return n;
}

int b(int l, int r) {
    if (l == r) {
        tr[nx] = 0;
        return nx++;
    }
    int mid = (l + r) / 2;
    lC[nx] = b(l, mid);
    rC[nx] = b(mid + 1, r);
    return nx++;
}

// q does not create any new nodes
int q(int i, int l, int r, int s, int e) {
    if (e < l || r < s) {
        return 0;
    }
    if (s <= l && r <= e) {
        return tr[i];
    }
    int mid = (l + r) / 2;
    return q(lC[i], l, mid, s, e) +
           q(rC[i], mid + 1, r, s, e);
}

// returns index of updated node
int u(int i, int l, int r, int x, int d) {
    i = cpy(i);
    if (l == r) {
        tr[i] += d;
        return i;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        lC[i] = u(lC[i], l, mid, x, d);
    } else {
        rC[i] = u(rC[i], mid + 1, r, x, d);
    }
    tr[i] = tr[lC[i]] + tr[rC[i]];
    return i;
}

int N, K;

pi c[MAXN];

int op[MAXN];

int rt[MAXN];

set<int> vals;
map<int, int> mp;
map<int, int> rMp;

int nV;

// search for first index with element in range
int binSearch(pi range) {
    int low = 1;
    int hi = K + 1;

    while (low != hi) {
        int mid = (low + hi) / 2;

        if (q(rt[mid], 0, nV, range.f, range.s) > 0) {
            hi = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        cin >> c[i].f >> c[i].s;
        vals.insert(c[i].f);
        vals.insert(c[i].s);
    }
    for (int i = 0; i < K; i++) {
        cin >> op[K - i];
        vals.insert(op[K - i]);
    }

    nV = 0;
    for (int x : vals) {
        mp[x] = nV;
        rMp[nV] = x;
        nV++;
    }

    for (int i = 0; i < N; i++) {
        c[i].f = mp[c[i].f];
        c[i].s = mp[c[i].s];
    }

    for (int i = 0; i < K; i++) {
        op[K - i] = mp[op[K - i]];
    }

    assert(nV <= MAXN);

    rt[0] = b(0, nV);
    for (int i = 1; i <= K; i++) {
        rt[i] = u(rt[i - 1], 0, nV, op[i], 1);
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
//        ps(c[i]);
        int small = min(c[i].f, c[i].s);
        int big = max(c[i].f, c[i].s);

        if (small == big) {
//            ps("add", rMp[small]);
            ans += rMp[small];
            continue;
        }

        int force = binSearch({small, big - 1});
//        ps(force);

        int flip = q(rt[force - 1], 0, nV, big, nV);

        if (force == K + 1 && c[i].f == small) flip++;

//        ps(flip);
        if (flip & 1) {
//            ps("add", rMp[small]);
            ans += rMp[small];
        } else {
//            ps("add", rMp[big]);
            ans += rMp[big];
        }
    }
    cout << ans << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 9 ms 896 KB Output is correct
13 Correct 9 ms 896 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 9 ms 896 KB Output is correct
13 Correct 9 ms 896 KB Output is correct
14 Correct 87 ms 7416 KB Output is correct
15 Correct 193 ms 14560 KB Output is correct
16 Correct 316 ms 21752 KB Output is correct
17 Correct 476 ms 29304 KB Output is correct
18 Correct 482 ms 29176 KB Output is correct
19 Correct 470 ms 29176 KB Output is correct
20 Correct 473 ms 29224 KB Output is correct
21 Correct 438 ms 29200 KB Output is correct
22 Correct 287 ms 22264 KB Output is correct
23 Correct 268 ms 18808 KB Output is correct
24 Correct 255 ms 16248 KB Output is correct
25 Correct 306 ms 24568 KB Output is correct
26 Correct 277 ms 21112 KB Output is correct
27 Correct 335 ms 22392 KB Output is correct
28 Correct 290 ms 22264 KB Output is correct
29 Correct 374 ms 25732 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 9 ms 896 KB Output is correct
13 Correct 9 ms 896 KB Output is correct
14 Correct 87 ms 7416 KB Output is correct
15 Correct 193 ms 14560 KB Output is correct
16 Correct 316 ms 21752 KB Output is correct
17 Correct 476 ms 29304 KB Output is correct
18 Correct 482 ms 29176 KB Output is correct
19 Correct 470 ms 29176 KB Output is correct
20 Correct 473 ms 29224 KB Output is correct
21 Correct 438 ms 29200 KB Output is correct
22 Correct 287 ms 22264 KB Output is correct
23 Correct 268 ms 18808 KB Output is correct
24 Correct 255 ms 16248 KB Output is correct
25 Correct 306 ms 24568 KB Output is correct
26 Correct 277 ms 21112 KB Output is correct
27 Correct 335 ms 22392 KB Output is correct
28 Correct 290 ms 22264 KB Output is correct
29 Correct 374 ms 25732 KB Output is correct
30 Correct 774 ms 82424 KB Output is correct
31 Correct 1410 ms 96888 KB Output is correct
32 Correct 2242 ms 114988 KB Output is correct
33 Execution timed out 3090 ms 149796 KB Time limit exceeded
34 Halted 0 ms 0 KB -