oj.uz

Submission #1111179

# Submission time Handle Problem Language Result Execution time Memory
1111179 2024-11-11T16:03:27 Z adaawf Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 236 ms 25420 KB 
#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005], c[200005], res[200005], t[2400005], tt[2400005], dd[200005], z = 0;
map<int, int> m;
vector<pair<int, int>> g[200005];
void update(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t[v] = max(t[v], y);
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
void update2(int v, int tl, int tr, int x) {
    if (tl == tr) {
        tt[v]++;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update2(v * 2, tl, mid, x);
    else update2(v * 2 + 1, mid + 1, tr, x);
    tt[v] = tt[v * 2] + tt[v * 2 + 1];
}
int sum2(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return tt[v];
    }
    int mid = (tl + tr) / 2;
    return sum2(v * 2, tl, mid, l, min(r, mid)) + sum2(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<int> v;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> c[i];
        v.push_back(c[i]);
    }
    sort(v.begin(), v.end());
    for (int w : v) {
        if (!m.count(w)) {
            m[w] = ++z;
            dd[z] = w;
        }
    }
    for (int i = 1; i <= n; i++) a[i] = m[a[i]], b[i] = m[b[i]];
    for (int i = 1; i <= q; i++) {
        c[i] = m[c[i]];
        update(1, 1, z, c[i], i);
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) res[i] = 1;
        else {
            if (a[i] < b[i]) {
                int h = sum(1, 1, z, a[i], b[i] - 1) + 1;
                if (h != 1) {
                    res[i] = 1;
                }
                g[h].push_back({i, b[i]});
            }
            else {
                int h = sum(1, 1, z, b[i], a[i] - 1) + 1;
                g[h].push_back({i, a[i]});
            }
        }
    }
    for (int i = q; i >= 1; i--) {
        update2(1, 1, z, c[i]);
        for (auto w : g[i]) {
            int h = sum2(1, 1, z, w.second, z);
            if (h & 1) res[w.first] ^= 1;
        }
    }
    long long int d = 0;
    for (int i = 1; i <= n; i++) {
        if (res[i] == 0) d += dd[a[i]];
        else d += dd[b[i]];
    }
    cout << d;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 4 ms 11256 KB Output is correct
4 Correct 4 ms 11088 KB Output is correct
5 Correct 4 ms 11088 KB Output is correct
6 Correct 4 ms 11088 KB Output is correct
7 Correct 4 ms 11088 KB Output is correct
8 Correct 3 ms 11088 KB Output is correct
9 Correct 4 ms 11088 KB Output is correct
10 Correct 3 ms 7168 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 4 ms 11000 KB Output is correct
13 Correct 3 ms 8948 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 4 ms 11256 KB Output is correct
4 Correct 4 ms 11088 KB Output is correct
5 Correct 4 ms 11088 KB Output is correct
6 Correct 4 ms 11088 KB Output is correct
7 Correct 4 ms 11088 KB Output is correct
8 Correct 3 ms 11088 KB Output is correct
9 Correct 4 ms 11088 KB Output is correct
10 Correct 3 ms 7168 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 4 ms 11000 KB Output is correct
13 Correct 3 ms 8948 KB Output is correct
14 Correct 22 ms 12880 KB Output is correct
15 Correct 55 ms 15224 KB Output is correct
16 Correct 78 ms 15824 KB Output is correct
17 Correct 107 ms 21704 KB Output is correct
18 Correct 113 ms 19656 KB Output is correct
19 Correct 105 ms 19704 KB Output is correct
20 Correct 106 ms 16340 KB Output is correct
21 Correct 107 ms 16584 KB Output is correct
22 Correct 74 ms 17296 KB Output is correct
23 Correct 70 ms 12232 KB Output is correct
24 Correct 65 ms 13256 KB Output is correct
25 Correct 78 ms 19664 KB Output is correct
26 Correct 74 ms 17352 KB Output is correct
27 Correct 86 ms 17872 KB Output is correct
28 Correct 82 ms 17780 KB Output is correct
29 Correct 92 ms 18836 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 4 ms 11256 KB Output is correct
4 Correct 4 ms 11088 KB Output is correct
5 Correct 4 ms 11088 KB Output is correct
6 Correct 4 ms 11088 KB Output is correct
7 Correct 4 ms 11088 KB Output is correct
8 Correct 3 ms 11088 KB Output is correct
9 Correct 4 ms 11088 KB Output is correct
10 Correct 3 ms 7168 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 4 ms 11000 KB Output is correct
13 Correct 3 ms 8948 KB Output is correct
14 Correct 22 ms 12880 KB Output is correct
15 Correct 55 ms 15224 KB Output is correct
16 Correct 78 ms 15824 KB Output is correct
17 Correct 107 ms 21704 KB Output is correct
18 Correct 113 ms 19656 KB Output is correct
19 Correct 105 ms 19704 KB Output is correct
20 Correct 106 ms 16340 KB Output is correct
21 Correct 107 ms 16584 KB Output is correct
22 Correct 74 ms 17296 KB Output is correct
23 Correct 70 ms 12232 KB Output is correct
24 Correct 65 ms 13256 KB Output is correct
25 Correct 78 ms 19664 KB Output is correct
26 Correct 74 ms 17352 KB Output is correct
27 Correct 86 ms 17872 KB Output is correct
28 Correct 82 ms 17780 KB Output is correct
29 Correct 92 ms 18836 KB Output is correct
30 Incorrect 236 ms 25420 KB Output isn't correct
31 Halted 0 ms 0 KB -