oj.uz

Submission #235436

# Submission time Handle Problem Language Result Execution time Memory
235436 2020-05-28T09:24:43 Z parsa_mobed Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1093 ms 117336 KB 
#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair <int , int>
#define F first
#define S second
#define Mx first
#define Mn second

const int N = 2e5 + 5, inf = 1e9 + 1;
int a[N], b[N], S[N], p[N], n, k, timer = 0;
pii A[N];

struct Node {
    vector <int> NQ, Suf;
    vector <pii> SQ;
} seg[N<<2];

void NOTQ(int l, int r, int L = 0, int R = n, int id = 1) {
    if (r <= L || R <= l) return ;
    if (l <= L && R <= r) {
        seg[id].NQ.push_back(timer);
        return ;
    }
    int mid = (L+R)>>1;
    NOTQ(l, r, L, mid, id<<1);
    NOTQ(l, r, mid, R, id<<1|1);
}
void SETQ(int l, int r, int val, int L = 0, int R = n, int id = 1) {
    if (r <= L || R <= l) return ;
    if (l <= L && R <= r) {
        seg[id].SQ.push_back({val, timer});
        return ;
    }
    int mid = (L+R)>>1;
    SETQ(l, r, val, L, mid, id<<1);
    SETQ(l, r, val, mid, R, id<<1|1);
}
int GET(int l, int L = 0, int R = n, int id = 1) {
    int t = 0;
    if (seg[id].SQ.size()) {
        int x = lower_bound(all(seg[id].SQ), make_pair(A[l].Mn, 0)) - seg[id].SQ.begin();
        t = seg[id].Suf[x];
    }
    if (R - L == 1) return t;
    int mid = (L+R)>>1;
    if (l < mid) return max(t, GET(l, L, mid, id<<1));
    else return max(t, GET(l, mid, R, id<<1|1));
}
int GET2(int l, int t, int L = 0, int R = n, int id = 1) {
    int r = 0;
    if (seg[id].NQ.size()) {
        int x = lower_bound(all(seg[id].NQ), t) - seg[id].NQ.begin();
        r = seg[id].NQ.size() - x;
    }
    if (R - L == 1) return r;
    int mid = (L+R)>>1;
    if (l < mid) return r + GET2(l, t, L, mid, id<<1);
    else return r + GET2(l, t, mid, R, id<<1|1);
}

void FixEverything(int L = 0, int R = n, int id = 1) {
    sort(all(seg[id].SQ)), sort(all(seg[id].NQ));
    seg[id].Suf.resize(seg[id].SQ.size() + 1);
    for (int i = seg[id].SQ.size() - 1; i >= 0; i--) seg[id].Suf[i] = max(seg[id].Suf[i+1], seg[id].SQ[i].S);
    if (R - L == 1) return ;
    int mid = (L+R)>>1;
    FixEverything(L, mid, id<<1);
    FixEverything(mid, R, id<<1|1);
}

bool cmp(int i, int j) {return A[i] < A[j];}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        A[i].Mn = a[i], A[i].Mx = b[i], p[i] = i;
        if (A[i].Mn > A[i].Mx) swap(A[i].Mn, A[i].Mx), S[i] = 1;
    }
    sort(p, p + n, cmp), sort(A, A + n);
    for (int i = 0; i < n; i++) if (S[p[i]] == 1) SETQ(i, i + 1, inf);
    for (timer++; timer <= k; timer++) {
        int t; cin >> t;
        int x = upper_bound(A, A + n, make_pair(t, inf)) - A;
        NOTQ(0, x), SETQ(x, n, t);
    }
    FixEverything();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int t = GET(i);
        int x = GET2(i, t)&1;
        if (t != 0) S[p[i]] = 1;
        if ((S[p[i]]^x) == 1) ans += A[i].Mx;
        else ans += A[i].Mn;
    }
    cout << ans << "\n";


    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56824 KB Output is correct
2 Correct 38 ms 56944 KB Output is correct
3 Correct 38 ms 56952 KB Output is correct
4 Correct 38 ms 56960 KB Output is correct
5 Correct 38 ms 56960 KB Output is correct
6 Correct 39 ms 56952 KB Output is correct
7 Correct 38 ms 56952 KB Output is correct
8 Correct 39 ms 56952 KB Output is correct
9 Correct 38 ms 56824 KB Output is correct
10 Correct 39 ms 56960 KB Output is correct
11 Correct 38 ms 56960 KB Output is correct
12 Correct 38 ms 56960 KB Output is correct
13 Correct 38 ms 56960 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56824 KB Output is correct
2 Correct 38 ms 56944 KB Output is correct
3 Correct 38 ms 56952 KB Output is correct
4 Correct 38 ms 56960 KB Output is correct
5 Correct 38 ms 56960 KB Output is correct
6 Correct 39 ms 56952 KB Output is correct
7 Correct 38 ms 56952 KB Output is correct
8 Correct 39 ms 56952 KB Output is correct
9 Correct 38 ms 56824 KB Output is correct
10 Correct 39 ms 56960 KB Output is correct
11 Correct 38 ms 56960 KB Output is correct
12 Correct 38 ms 56960 KB Output is correct
13 Correct 38 ms 56960 KB Output is correct
14 Correct 65 ms 59576 KB Output is correct
15 Correct 97 ms 62456 KB Output is correct
16 Correct 136 ms 65588 KB Output is correct
17 Correct 178 ms 68724 KB Output is correct
18 Correct 177 ms 68720 KB Output is correct
19 Correct 163 ms 66808 KB Output is correct
20 Correct 181 ms 68852 KB Output is correct
21 Correct 124 ms 63988 KB Output is correct
22 Correct 130 ms 65016 KB Output is correct
23 Correct 144 ms 65656 KB Output is correct
24 Correct 160 ms 67316 KB Output is correct
25 Correct 107 ms 63732 KB Output is correct
26 Correct 145 ms 67296 KB Output is correct
27 Correct 168 ms 68444 KB Output is correct
28 Correct 139 ms 66936 KB Output is correct
29 Correct 178 ms 68728 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56824 KB Output is correct
2 Correct 38 ms 56944 KB Output is correct
3 Correct 38 ms 56952 KB Output is correct
4 Correct 38 ms 56960 KB Output is correct
5 Correct 38 ms 56960 KB Output is correct
6 Correct 39 ms 56952 KB Output is correct
7 Correct 38 ms 56952 KB Output is correct
8 Correct 39 ms 56952 KB Output is correct
9 Correct 38 ms 56824 KB Output is correct
10 Correct 39 ms 56960 KB Output is correct
11 Correct 38 ms 56960 KB Output is correct
12 Correct 38 ms 56960 KB Output is correct
13 Correct 38 ms 56960 KB Output is correct
14 Correct 65 ms 59576 KB Output is correct
15 Correct 97 ms 62456 KB Output is correct
16 Correct 136 ms 65588 KB Output is correct
17 Correct 178 ms 68724 KB Output is correct
18 Correct 177 ms 68720 KB Output is correct
19 Correct 163 ms 66808 KB Output is correct
20 Correct 181 ms 68852 KB Output is correct
21 Correct 124 ms 63988 KB Output is correct
22 Correct 130 ms 65016 KB Output is correct
23 Correct 144 ms 65656 KB Output is correct
24 Correct 160 ms 67316 KB Output is correct
25 Correct 107 ms 63732 KB Output is correct
26 Correct 145 ms 67296 KB Output is correct
27 Correct 168 ms 68444 KB Output is correct
28 Correct 139 ms 66936 KB Output is correct
29 Correct 178 ms 68728 KB Output is correct
30 Correct 340 ms 85080 KB Output is correct
31 Correct 614 ms 96108 KB Output is correct
32 Correct 791 ms 103628 KB Output is correct
33 Correct 1038 ms 117080 KB Output is correct
34 Correct 82 ms 60936 KB Output is correct
35 Correct 1059 ms 117252 KB Output is correct
36 Correct 1093 ms 117336 KB Output is correct
37 Correct 1031 ms 117240 KB Output is correct
38 Correct 890 ms 106972 KB Output is correct
39 Correct 1040 ms 116964 KB Output is correct
40 Correct 440 ms 87396 KB Output is correct
41 Correct 1010 ms 114260 KB Output is correct
42 Correct 1024 ms 116068 KB Output is correct
43 Correct 241 ms 79596 KB Output is correct
44 Correct 242 ms 79596 KB Output is correct
45 Correct 251 ms 79808 KB Output is correct
46 Correct 767 ms 105824 KB Output is correct
47 Correct 952 ms 114264 KB Output is correct
48 Correct 816 ms 114156 KB Output is correct
49 Correct 776 ms 106340 KB Output is correct