oj.uz

Submission #228177

# Submission time Handle Problem Language Result Execution time Memory
228177 2020-04-30T06:06:56 Z tri Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 815 ms 166648 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 = 7 * 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 640 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 1152 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 8 ms 640 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 640 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 1152 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 8 ms 640 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 90 ms 7288 KB Output is correct
15 Correct 195 ms 14552 KB Output is correct
16 Correct 340 ms 21748 KB Output is correct
17 Correct 482 ms 29272 KB Output is correct
18 Correct 465 ms 29176 KB Output is correct
19 Correct 478 ms 29304 KB Output is correct
20 Correct 458 ms 29176 KB Output is correct
21 Correct 437 ms 29164 KB Output is correct
22 Correct 297 ms 22392 KB Output is correct
23 Correct 262 ms 18936 KB Output is correct
24 Correct 242 ms 16120 KB Output is correct
25 Correct 306 ms 24568 KB Output is correct
26 Correct 289 ms 21232 KB Output is correct
27 Correct 345 ms 22392 KB Output is correct
28 Correct 298 ms 22520 KB Output is correct
29 Correct 375 ms 25720 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 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 1152 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 8 ms 640 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 90 ms 7288 KB Output is correct
15 Correct 195 ms 14552 KB Output is correct
16 Correct 340 ms 21748 KB Output is correct
17 Correct 482 ms 29272 KB Output is correct
18 Correct 465 ms 29176 KB Output is correct
19 Correct 478 ms 29304 KB Output is correct
20 Correct 458 ms 29176 KB Output is correct
21 Correct 437 ms 29164 KB Output is correct
22 Correct 297 ms 22392 KB Output is correct
23 Correct 262 ms 18936 KB Output is correct
24 Correct 242 ms 16120 KB Output is correct
25 Correct 306 ms 24568 KB Output is correct
26 Correct 289 ms 21232 KB Output is correct
27 Correct 345 ms 22392 KB Output is correct
28 Correct 298 ms 22520 KB Output is correct
29 Correct 375 ms 25720 KB Output is correct
30 Runtime error 815 ms 166648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -