oj.uz

Submission #228175

# Submission time Handle Problem Language Result Execution time Memory
228175 2020-04-30T06:04:00 Z tri Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 149672 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

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


static const int MAXN = 600100, NODES = 10 * 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 768 KB Output is correct
3 Correct 10 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 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 768 KB Output is correct
3 Correct 10 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 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 200 ms 14584 KB Output is correct
16 Correct 345 ms 21992 KB Output is correct
17 Correct 466 ms 29176 KB Output is correct
18 Correct 461 ms 29304 KB Output is correct
19 Correct 485 ms 29304 KB Output is correct
20 Correct 476 ms 29176 KB Output is correct
21 Correct 441 ms 29176 KB Output is correct
22 Correct 292 ms 22392 KB Output is correct
23 Correct 261 ms 18812 KB Output is correct
24 Correct 247 ms 16248 KB Output is correct
25 Correct 304 ms 24440 KB Output is correct
26 Correct 286 ms 21112 KB Output is correct
27 Correct 374 ms 22268 KB Output is correct
28 Correct 302 ms 22520 KB Output is correct
29 Correct 372 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 768 KB Output is correct
3 Correct 10 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 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 200 ms 14584 KB Output is correct
16 Correct 345 ms 21992 KB Output is correct
17 Correct 466 ms 29176 KB Output is correct
18 Correct 461 ms 29304 KB Output is correct
19 Correct 485 ms 29304 KB Output is correct
20 Correct 476 ms 29176 KB Output is correct
21 Correct 441 ms 29176 KB Output is correct
22 Correct 292 ms 22392 KB Output is correct
23 Correct 261 ms 18812 KB Output is correct
24 Correct 247 ms 16248 KB Output is correct
25 Correct 304 ms 24440 KB Output is correct
26 Correct 286 ms 21112 KB Output is correct
27 Correct 374 ms 22268 KB Output is correct
28 Correct 302 ms 22520 KB Output is correct
29 Correct 372 ms 25720 KB Output is correct
30 Correct 787 ms 82552 KB Output is correct
31 Correct 1373 ms 96828 KB Output is correct
32 Correct 2294 ms 114932 KB Output is correct
33 Execution timed out 3086 ms 149672 KB Time limit exceeded
34 Halted 0 ms 0 KB -