oj.uz

Submission #228176

# Submission time Handle Problem Language Result Execution time Memory
228176 2020-04-30T06:06:26 Z tri Fortune Telling 2 (JOI14_fortune_telling2) C++11
35 / 100
 661 ms 137692 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 = 5 * 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 10 ms 1024 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 12 ms 1024 KB Output is correct
9 Correct 9 ms 952 KB Output is correct
10 Correct 7 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 10 ms 1024 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 12 ms 1024 KB Output is correct
9 Correct 9 ms 952 KB Output is correct
10 Correct 7 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 86 ms 7288 KB Output is correct
15 Correct 189 ms 14636 KB Output is correct
16 Correct 327 ms 21752 KB Output is correct
17 Correct 492 ms 29164 KB Output is correct
18 Correct 455 ms 29176 KB Output is correct
19 Correct 479 ms 29304 KB Output is correct
20 Correct 452 ms 29176 KB Output is correct
21 Correct 434 ms 29436 KB Output is correct
22 Correct 286 ms 22264 KB Output is correct
23 Correct 271 ms 18944 KB Output is correct
24 Correct 246 ms 16120 KB Output is correct
25 Correct 301 ms 24316 KB Output is correct
26 Correct 283 ms 21112 KB Output is correct
27 Correct 346 ms 22264 KB Output is correct
28 Correct 298 ms 22264 KB Output is correct
29 Correct 371 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 10 ms 1024 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 12 ms 1024 KB Output is correct
9 Correct 9 ms 952 KB Output is correct
10 Correct 7 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 86 ms 7288 KB Output is correct
15 Correct 189 ms 14636 KB Output is correct
16 Correct 327 ms 21752 KB Output is correct
17 Correct 492 ms 29164 KB Output is correct
18 Correct 455 ms 29176 KB Output is correct
19 Correct 479 ms 29304 KB Output is correct
20 Correct 452 ms 29176 KB Output is correct
21 Correct 434 ms 29436 KB Output is correct
22 Correct 286 ms 22264 KB Output is correct
23 Correct 271 ms 18944 KB Output is correct
24 Correct 246 ms 16120 KB Output is correct
25 Correct 301 ms 24316 KB Output is correct
26 Correct 283 ms 21112 KB Output is correct
27 Correct 346 ms 22264 KB Output is correct
28 Correct 298 ms 22264 KB Output is correct
29 Correct 371 ms 25720 KB Output is correct
30 Runtime error 661 ms 137692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -