oj.uz

Submission #498592

# Submission time Handle Problem Language Result Execution time Memory
498592 2021-12-25T15:27:57 Z khoabright Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 460 ms 59936 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()

const int N = 6e5 + 5;

struct mst{
    vector<vector<int>> node;
    int sz = 1;

    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < a.size()) {
                node[x].resize(1, a[lx]);
            }
            return;
        }

        int m = (lx + rx) >> 1;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);

        merge(all(node[2 * x + 1]), all(node[2 * x + 2]), back_inserter(node[x]));
    }

    void init(vector<int> &a) {
        int SIZE = a.size();
        while (sz < SIZE) sz *= 2;
        node.resize(2 * sz);
        build(a, 0, 0, sz);
    }

    int bigger(int l, int r, int k, int x, int lx, int rx) {
        if (rx <= l || r <= lx) return 0;
        if (l <= lx && rx <= r) {
            auto &v = node[x];
            auto it = upper_bound(all(v), k);
            int res = v.end() - it;
            return res;
        }

        int m = (lx + rx) >> 1;
        int s1 = bigger(l, r, k, 2 * x + 1, lx, m);
        int s2 = bigger(l, r, k, 2 * x + 2, m, rx);

        return s1 + s2;
    }

    int bigger(int l, int r, int k) {return bigger(l, r, k, 0, 0, sz);}
};

struct segtree {
    int sz = 1;
    vector<int> maxi;

    void init(int SIZE) {
        while (sz < SIZE) sz *= 2;
        maxi.resize(2 * sz);
    }

    void update(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            maxi[x] = v;
            return;
        }

        int m = (lx + rx) >> 1;
        if (i < m) update(i, v, 2 * x + 1, lx, m);
        else update(i, v, 2 * x + 2, m, rx);
        maxi[x] = max(maxi[2 * x + 1], maxi[2 * x + 2]);
    }
    void update(int i, int v) {update(i, v, 0, 0, sz);}

    int query(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx) return 0;
        if (l <= lx && rx <= r) return maxi[x];
        int m = (lx + rx) >> 1;
        return max(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
    }
    int query(int l, int r) {return query(l, r, 0, 0, sz);}
};

int pos[N];

void solve() {
    int n, k; cin >> n >> k;
    vector<int> comp;
    vector<int> a(n + 1), b(n + 1), c(k + 1), sig(n + 1);
    rep(i, 1, n) {
        cin >> a[i] >> b[i];
        sig[i] = (a[i] <= b[i]);
        if (a[i] > b[i]) swap(a[i], b[i]);
        comp.pb(a[i]);
        comp.pb(b[i]);
    }
    rep(i, 1, k) {
        cin >> c[i];
        comp.pb(c[i]);
    }

    sort(all(comp));

    rep(i, 1, n) {
        a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
        b[i] = lower_bound(all(comp), b[i]) - comp.begin() + 1;
    }
    rep(i, 1, k) {
        c[i] = lower_bound(all(comp), c[i]) - comp.begin() + 1;
        pos[c[i]] = max(pos[c[i]], i);
    }

    segtree st;
    mst st1;
    st1.init(c);

    st.init(N + 5);
    rep(i, 1, N - 1) {
        st.update(i, pos[i]);
    }

    ll sum = 0;

    rep(i, 1, n) {
        int mx = st.query(a[i], b[i]);
        int cnt = st1.bigger(mx + 1, k + 1, b[i] - 1);
        if (mx) sig[i] = 0;
        sig[i] ^= (cnt & 1);
        int res;
        if (sig[i]) res = min(a[i], b[i]);
        else res = max(a[i], b[i]);
        res = comp[res - 1];
        sum += res;
    }
    cout << sum;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message

fortune_telling2.cpp: In member function 'void mst::build(std::vector<int>&, int, int, int)':
fortune_telling2.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8652 KB Output is correct
2 Correct 51 ms 8648 KB Output is correct
3 Correct 51 ms 8772 KB Output is correct
4 Correct 49 ms 8692 KB Output is correct
5 Correct 54 ms 8652 KB Output is correct
6 Correct 50 ms 8640 KB Output is correct
7 Correct 53 ms 8772 KB Output is correct
8 Correct 53 ms 8652 KB Output is correct
9 Correct 51 ms 8652 KB Output is correct
10 Correct 50 ms 8652 KB Output is correct
11 Correct 53 ms 8632 KB Output is correct
12 Correct 52 ms 8628 KB Output is correct
13 Correct 54 ms 8772 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8652 KB Output is correct
2 Correct 51 ms 8648 KB Output is correct
3 Correct 51 ms 8772 KB Output is correct
4 Correct 49 ms 8692 KB Output is correct
5 Correct 54 ms 8652 KB Output is correct
6 Correct 50 ms 8640 KB Output is correct
7 Correct 53 ms 8772 KB Output is correct
8 Correct 53 ms 8652 KB Output is correct
9 Correct 51 ms 8652 KB Output is correct
10 Correct 50 ms 8652 KB Output is correct
11 Correct 53 ms 8632 KB Output is correct
12 Correct 52 ms 8628 KB Output is correct
13 Correct 54 ms 8772 KB Output is correct
14 Correct 65 ms 11084 KB Output is correct
15 Correct 83 ms 13696 KB Output is correct
16 Correct 99 ms 15552 KB Output is correct
17 Correct 121 ms 19176 KB Output is correct
18 Correct 116 ms 19112 KB Output is correct
19 Correct 118 ms 19108 KB Output is correct
20 Correct 135 ms 19124 KB Output is correct
21 Correct 113 ms 19148 KB Output is correct
22 Correct 100 ms 18788 KB Output is correct
23 Correct 101 ms 18628 KB Output is correct
24 Correct 108 ms 18636 KB Output is correct
25 Correct 102 ms 18656 KB Output is correct
26 Correct 108 ms 18880 KB Output is correct
27 Correct 132 ms 19184 KB Output is correct
28 Correct 116 ms 19132 KB Output is correct
29 Correct 153 ms 19176 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8652 KB Output is correct
2 Correct 51 ms 8648 KB Output is correct
3 Correct 51 ms 8772 KB Output is correct
4 Correct 49 ms 8692 KB Output is correct
5 Correct 54 ms 8652 KB Output is correct
6 Correct 50 ms 8640 KB Output is correct
7 Correct 53 ms 8772 KB Output is correct
8 Correct 53 ms 8652 KB Output is correct
9 Correct 51 ms 8652 KB Output is correct
10 Correct 50 ms 8652 KB Output is correct
11 Correct 53 ms 8632 KB Output is correct
12 Correct 52 ms 8628 KB Output is correct
13 Correct 54 ms 8772 KB Output is correct
14 Correct 65 ms 11084 KB Output is correct
15 Correct 83 ms 13696 KB Output is correct
16 Correct 99 ms 15552 KB Output is correct
17 Correct 121 ms 19176 KB Output is correct
18 Correct 116 ms 19112 KB Output is correct
19 Correct 118 ms 19108 KB Output is correct
20 Correct 135 ms 19124 KB Output is correct
21 Correct 113 ms 19148 KB Output is correct
22 Correct 100 ms 18788 KB Output is correct
23 Correct 101 ms 18628 KB Output is correct
24 Correct 108 ms 18636 KB Output is correct
25 Correct 102 ms 18656 KB Output is correct
26 Correct 108 ms 18880 KB Output is correct
27 Correct 132 ms 19184 KB Output is correct
28 Correct 116 ms 19132 KB Output is correct
29 Correct 153 ms 19176 KB Output is correct
30 Correct 206 ms 50804 KB Output is correct
31 Correct 251 ms 52744 KB Output is correct
32 Correct 311 ms 55092 KB Output is correct
33 Correct 431 ms 59820 KB Output is correct
34 Correct 185 ms 50664 KB Output is correct
35 Correct 455 ms 59828 KB Output is correct
36 Correct 459 ms 59760 KB Output is correct
37 Correct 460 ms 59836 KB Output is correct
38 Correct 439 ms 59936 KB Output is correct
39 Correct 445 ms 59724 KB Output is correct
40 Correct 415 ms 59700 KB Output is correct
41 Correct 436 ms 59892 KB Output is correct
42 Correct 439 ms 59856 KB Output is correct
43 Correct 328 ms 58048 KB Output is correct
44 Correct 347 ms 58076 KB Output is correct
45 Correct 323 ms 58496 KB Output is correct
46 Correct 331 ms 57908 KB Output is correct
47 Correct 352 ms 57796 KB Output is correct
48 Correct 443 ms 59128 KB Output is correct
49 Correct 414 ms 59064 KB Output is correct