oj.uz

Submission #228174

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

// 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, MAXN, 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]);
    }

    int 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, MAXN);
    for (int i = 1; i <= K; i++) {
        rt[i] = u(rt[i - 1], 0, MAXN, 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, MAXN, big, MAXN);

        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 17 ms 14848 KB Output is correct
2 Correct 20 ms 14976 KB Output is correct
3 Correct 22 ms 15104 KB Output is correct
4 Correct 22 ms 15232 KB Output is correct
5 Correct 22 ms 15104 KB Output is correct
6 Correct 22 ms 15104 KB Output is correct
7 Correct 21 ms 15104 KB Output is correct
8 Correct 22 ms 15232 KB Output is correct
9 Correct 21 ms 15104 KB Output is correct
10 Correct 19 ms 14848 KB Output is correct
11 Correct 21 ms 15104 KB Output is correct
12 Correct 21 ms 14976 KB Output is correct
13 Correct 21 ms 14976 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14848 KB Output is correct
2 Correct 20 ms 14976 KB Output is correct
3 Correct 22 ms 15104 KB Output is correct
4 Correct 22 ms 15232 KB Output is correct
5 Correct 22 ms 15104 KB Output is correct
6 Correct 22 ms 15104 KB Output is correct
7 Correct 21 ms 15104 KB Output is correct
8 Correct 22 ms 15232 KB Output is correct
9 Correct 21 ms 15104 KB Output is correct
10 Correct 19 ms 14848 KB Output is correct
11 Correct 21 ms 15104 KB Output is correct
12 Correct 21 ms 14976 KB Output is correct
13 Correct 21 ms 14976 KB Output is correct
14 Correct 111 ms 21496 KB Output is correct
15 Correct 229 ms 28536 KB Output is correct
16 Correct 359 ms 35576 KB Output is correct
17 Correct 491 ms 42744 KB Output is correct
18 Correct 492 ms 42632 KB Output is correct
19 Correct 489 ms 42616 KB Output is correct
20 Correct 511 ms 42744 KB Output is correct
21 Correct 463 ms 42616 KB Output is correct
22 Correct 319 ms 36600 KB Output is correct
23 Correct 291 ms 33784 KB Output is correct
24 Correct 259 ms 31736 KB Output is correct
25 Correct 309 ms 38140 KB Output is correct
26 Correct 292 ms 35960 KB Output is correct
27 Correct 362 ms 36984 KB Output is correct
28 Correct 330 ms 36984 KB Output is correct
29 Correct 418 ms 39968 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14848 KB Output is correct
2 Correct 20 ms 14976 KB Output is correct
3 Correct 22 ms 15104 KB Output is correct
4 Correct 22 ms 15232 KB Output is correct
5 Correct 22 ms 15104 KB Output is correct
6 Correct 22 ms 15104 KB Output is correct
7 Correct 21 ms 15104 KB Output is correct
8 Correct 22 ms 15232 KB Output is correct
9 Correct 21 ms 15104 KB Output is correct
10 Correct 19 ms 14848 KB Output is correct
11 Correct 21 ms 15104 KB Output is correct
12 Correct 21 ms 14976 KB Output is correct
13 Correct 21 ms 14976 KB Output is correct
14 Correct 111 ms 21496 KB Output is correct
15 Correct 229 ms 28536 KB Output is correct
16 Correct 359 ms 35576 KB Output is correct
17 Correct 491 ms 42744 KB Output is correct
18 Correct 492 ms 42632 KB Output is correct
19 Correct 489 ms 42616 KB Output is correct
20 Correct 511 ms 42744 KB Output is correct
21 Correct 463 ms 42616 KB Output is correct
22 Correct 319 ms 36600 KB Output is correct
23 Correct 291 ms 33784 KB Output is correct
24 Correct 259 ms 31736 KB Output is correct
25 Correct 309 ms 38140 KB Output is correct
26 Correct 292 ms 35960 KB Output is correct
27 Correct 362 ms 36984 KB Output is correct
28 Correct 330 ms 36984 KB Output is correct
29 Correct 418 ms 39968 KB Output is correct
30 Correct 775 ms 96760 KB Output is correct
31 Correct 1429 ms 109248 KB Output is correct
32 Correct 2230 ms 124664 KB Output is correct
33 Execution timed out 3094 ms 155768 KB Time limit exceeded
34 Halted 0 ms 0 KB -