oj.uz

Submission #1084965

# Submission time Handle Problem Language Result Execution time Memory
1084965 2024-09-07T09:12:08 Z pemguimn Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 324 ms 29372 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, VAL = 3 * N, MAX = 4 * VAL;
int n, k, a[N], b[N], t[N], pos[N];

int ans[N];

int seg[MAX];
vector<int> val;

void upd(int id, int tl, int tr, int i, int x){
    if(i < tl || i > tr) return;
    if(tl == tr){
        seg[id] = max(seg[id], x); return;
    }
    int mid = (tl + tr) / 2;
    upd(id * 2, tl, mid, i, x), upd(id * 2 + 1, mid + 1, tr, i, x);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

int query(int id, int tl, int tr, int l, int r){
    if(r < tl || tr < l) return 0;
    if(l <= tl && tr <= r) return seg[id];
    int mid = (tl + tr) / 2;
    return max(query(id * 2, tl, mid, l, r), query(id * 2 + 1, mid + 1, tr, l, r));
}

int bit[MAX];

void upd(int x, int val){
    for(; x < MAX; x += x & -x){
        bit[x] += val;
    }
}

void upd(int l, int r, int val){
    l++, r++;
    upd(l, val), upd(r + 1, -val);
}

int query(int x){
    x++;
    int ans = 0;
    for(; x; x -= x & -x) ans += bit[x];
    return ans;
}
vector<int> p[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);


    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i], val.insert(val.end(), {a[i], b[i]});
    for(int i = 1; i <= k; i++) cin >> t[i], val.push_back(t[i]);

    sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
    for(int i = 1; i <= n; i++) a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin(), b[i] = lower_bound(val.begin(), val.end(), b[i]) - val.begin();
    for(int i = 1; i <= k; i++) t[i] = lower_bound(val.begin(), val.end(), t[i]) - val.begin();

    for(int i = 1; i <= k; i++) upd(1, 0, val.size() - 1, t[i], i);

    for(int i = 1; i <= n; i++){
        pos[i] = query(1, 0, val.size() - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);
        p[pos[i]].push_back(i);
    }

    for(int i = k; i >= 0; i--){
        if(i) upd(0, t[i], 1);
        for(int x : p[i]){
            int cnt = query(max(a[x], b[x]));
            if(i == 0){
                ans[x] = (cnt & 1 ? b[x] : a[x]);
            } else{
                if(a[x] > b[x]) swap(a[x], b[x]);
                ans[x] = (cnt & 1 ? a[x] : b[x]);
            }
        }
    }

    long long res = 0;
    for(int i = 1; i <= n; i++) res += val[ans[i]];
    cout << res << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5184 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5288 KB Output is correct
13 Correct 3 ms 5240 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5184 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5288 KB Output is correct
13 Correct 3 ms 5240 KB Output is correct
14 Correct 15 ms 6124 KB Output is correct
15 Correct 27 ms 7148 KB Output is correct
16 Correct 40 ms 8404 KB Output is correct
17 Correct 55 ms 9168 KB Output is correct
18 Correct 61 ms 9168 KB Output is correct
19 Correct 56 ms 9168 KB Output is correct
20 Correct 65 ms 9172 KB Output is correct
21 Correct 53 ms 9424 KB Output is correct
22 Correct 42 ms 8656 KB Output is correct
23 Correct 40 ms 8092 KB Output is correct
24 Correct 39 ms 7892 KB Output is correct
25 Correct 41 ms 8780 KB Output is correct
26 Correct 49 ms 8740 KB Output is correct
27 Correct 47 ms 9168 KB Output is correct
28 Correct 46 ms 9148 KB Output is correct
29 Correct 56 ms 9344 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5184 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5288 KB Output is correct
13 Correct 3 ms 5240 KB Output is correct
14 Correct 15 ms 6124 KB Output is correct
15 Correct 27 ms 7148 KB Output is correct
16 Correct 40 ms 8404 KB Output is correct
17 Correct 55 ms 9168 KB Output is correct
18 Correct 61 ms 9168 KB Output is correct
19 Correct 56 ms 9168 KB Output is correct
20 Correct 65 ms 9172 KB Output is correct
21 Correct 53 ms 9424 KB Output is correct
22 Correct 42 ms 8656 KB Output is correct
23 Correct 40 ms 8092 KB Output is correct
24 Correct 39 ms 7892 KB Output is correct
25 Correct 41 ms 8780 KB Output is correct
26 Correct 49 ms 8740 KB Output is correct
27 Correct 47 ms 9168 KB Output is correct
28 Correct 46 ms 9148 KB Output is correct
29 Correct 56 ms 9344 KB Output is correct
30 Correct 127 ms 11980 KB Output is correct
31 Correct 161 ms 16324 KB Output is correct
32 Correct 215 ms 19140 KB Output is correct
33 Correct 319 ms 29072 KB Output is correct
34 Correct 111 ms 11636 KB Output is correct
35 Correct 324 ms 28992 KB Output is correct
36 Correct 321 ms 28864 KB Output is correct
37 Correct 323 ms 28860 KB Output is correct
38 Correct 309 ms 28872 KB Output is correct
39 Correct 312 ms 28808 KB Output is correct
40 Correct 307 ms 29372 KB Output is correct
41 Correct 311 ms 28832 KB Output is correct
42 Correct 316 ms 28868 KB Output is correct
43 Correct 222 ms 24004 KB Output is correct
44 Correct 222 ms 24684 KB Output is correct
45 Correct 239 ms 25788 KB Output is correct
46 Correct 217 ms 21692 KB Output is correct
47 Correct 210 ms 18880 KB Output is correct
48 Correct 257 ms 24092 KB Output is correct
49 Correct 238 ms 24252 KB Output is correct