oj.uz

Submission #1029997

# Submission time Handle Problem Language Result Execution time Memory
1029997 2024-07-21T15:37:48 Z KienTran Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 469 ms 156568 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 6e5 + 5;
const int N = (1 << 20) + 5;
const int mod = 1e9 + 7; //998244353;
const int inf = 1e14;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, k, a[O], b[O], t[O], id[O], res[O], tree[O * 4], f[21][O];
vector <int> val, g[O], q[O];

bool how_sort(int x, int y){
    return max(a[x], b[x]) < max(a[y], b[y]);
}

void Build(int id, int l, int r){
    if (l == r){
        tree[id] = 1;
        return;
    }
    int mid = (l + r) / 2;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

void Update(int id, int l, int r, int u, int x){
    if (l > u || r < u) return;
    if (l == r){
        tree[id] = x;
        return;
    }
    int mid = (l + r) / 2;
    Update(id << 1, l, mid, u, x);
    Update(id << 1 | 1, mid + 1, r, u, x);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

int Get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l + r) / 2;
    return Get(id << 1, l, mid, u, v) + Get(id << 1 | 1, mid + 1, r, u, v);
}

int Get(int l, int r){
    int len = log2(r - l + 1);
    return max(f[len][l], f[len][r - (1 << len) + 1]);
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i){
        cin >> a[i] >> b[i];
        val.push_back(a[i]);
        val.push_back(b[i]);
        id[i] = i;
        if (a[i] == b[i]) res[i] = a[i];
    }

    for (int i = 1; i <= k; ++ i){
        cin >> t[i];
        val.push_back(t[i]);
    }

    sort(val.begin(), val.end());
    int m = unique(val.begin(), val.end()) - val.begin();
    val.resize(m);

    sort(id + 1, id + n + 1, how_sort);

    for (int i = 1; i <= n; ++ i){
        int j = id[i];
        if (a[j] == b[j]) continue;
        int d = upper_bound(val.begin(), val.end(), max(a[j], b[j])) - val.begin();
        q[d].push_back(j);
    }

    for (int i = 1; i <= k; ++ i){
        int d = upper_bound(val.begin(), val.end(), t[i]) - val.begin();
        g[d].push_back(i);
        f[0][d] = max(f[0][d], i);
    }

    for (int i = 1; i <= 20; ++ i){
        for (int j = 1; j - 1 + (1 << i) <= m; ++ j){
            f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
        }
    }

    Build(1, 1, k);

    int Max = 0;
    for (int i = 1; i <= m; ++ i){
        for (int j : q[i]){
            int idL = upper_bound(val.begin(), val.end(), min(a[j], b[j])) - val.begin();
            int idR = upper_bound(val.begin(), val.end(), max(a[j], b[j])) - val.begin() - 1;

            int x = Get(idL, idR);

            int cur = (a[j] < b[j]);
            if (x) cur = 0;

            cur ^= (Get(1, 1, k, x + 1, k) & 1);

            res[j] = (cur ? min(a[j], b[j]) : max(a[j], b[j]));
        }

        for (int j : g[i]){
            Update(1, 1, k, j, 0);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++ i){
        ans += res[i];
    }

    cout << ans;
}
/**
**/

Compilation message

fortune_telling2.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:97:9: warning: unused variable 'Max' [-Wunused-variable]
   97 |     int Max = 0;
      |         ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53852 KB Output is correct
2 Correct 8 ms 54140 KB Output is correct
3 Correct 10 ms 54088 KB Output is correct
4 Correct 10 ms 56196 KB Output is correct
5 Correct 10 ms 54108 KB Output is correct
6 Correct 10 ms 54108 KB Output is correct
7 Correct 10 ms 56156 KB Output is correct
8 Correct 10 ms 54108 KB Output is correct
9 Correct 9 ms 54108 KB Output is correct
10 Correct 9 ms 56156 KB Output is correct
11 Correct 10 ms 54108 KB Output is correct
12 Correct 10 ms 54108 KB Output is correct
13 Correct 10 ms 54108 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53852 KB Output is correct
2 Correct 8 ms 54140 KB Output is correct
3 Correct 10 ms 54088 KB Output is correct
4 Correct 10 ms 56196 KB Output is correct
5 Correct 10 ms 54108 KB Output is correct
6 Correct 10 ms 54108 KB Output is correct
7 Correct 10 ms 56156 KB Output is correct
8 Correct 10 ms 54108 KB Output is correct
9 Correct 9 ms 54108 KB Output is correct
10 Correct 9 ms 56156 KB Output is correct
11 Correct 10 ms 54108 KB Output is correct
12 Correct 10 ms 54108 KB Output is correct
13 Correct 10 ms 54108 KB Output is correct
14 Correct 26 ms 56800 KB Output is correct
15 Correct 40 ms 60732 KB Output is correct
16 Correct 61 ms 65656 KB Output is correct
17 Correct 66 ms 68560 KB Output is correct
18 Correct 79 ms 68560 KB Output is correct
19 Correct 72 ms 68488 KB Output is correct
20 Correct 85 ms 69804 KB Output is correct
21 Correct 65 ms 68528 KB Output is correct
22 Correct 51 ms 65740 KB Output is correct
23 Correct 60 ms 62796 KB Output is correct
24 Correct 60 ms 59720 KB Output is correct
25 Correct 56 ms 61036 KB Output is correct
26 Correct 53 ms 57620 KB Output is correct
27 Correct 80 ms 58832 KB Output is correct
28 Correct 65 ms 52652 KB Output is correct
29 Correct 77 ms 56780 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53852 KB Output is correct
2 Correct 8 ms 54140 KB Output is correct
3 Correct 10 ms 54088 KB Output is correct
4 Correct 10 ms 56196 KB Output is correct
5 Correct 10 ms 54108 KB Output is correct
6 Correct 10 ms 54108 KB Output is correct
7 Correct 10 ms 56156 KB Output is correct
8 Correct 10 ms 54108 KB Output is correct
9 Correct 9 ms 54108 KB Output is correct
10 Correct 9 ms 56156 KB Output is correct
11 Correct 10 ms 54108 KB Output is correct
12 Correct 10 ms 54108 KB Output is correct
13 Correct 10 ms 54108 KB Output is correct
14 Correct 26 ms 56800 KB Output is correct
15 Correct 40 ms 60732 KB Output is correct
16 Correct 61 ms 65656 KB Output is correct
17 Correct 66 ms 68560 KB Output is correct
18 Correct 79 ms 68560 KB Output is correct
19 Correct 72 ms 68488 KB Output is correct
20 Correct 85 ms 69804 KB Output is correct
21 Correct 65 ms 68528 KB Output is correct
22 Correct 51 ms 65740 KB Output is correct
23 Correct 60 ms 62796 KB Output is correct
24 Correct 60 ms 59720 KB Output is correct
25 Correct 56 ms 61036 KB Output is correct
26 Correct 53 ms 57620 KB Output is correct
27 Correct 80 ms 58832 KB Output is correct
28 Correct 65 ms 52652 KB Output is correct
29 Correct 77 ms 56780 KB Output is correct
30 Correct 183 ms 82664 KB Output is correct
31 Correct 258 ms 95520 KB Output is correct
32 Correct 290 ms 116000 KB Output is correct
33 Correct 409 ms 154360 KB Output is correct
34 Correct 167 ms 78964 KB Output is correct
35 Correct 460 ms 154268 KB Output is correct
36 Correct 469 ms 155304 KB Output is correct
37 Correct 442 ms 155372 KB Output is correct
38 Correct 452 ms 156084 KB Output is correct
39 Correct 399 ms 156568 KB Output is correct
40 Correct 395 ms 156084 KB Output is correct
41 Correct 391 ms 156240 KB Output is correct
42 Correct 388 ms 155724 KB Output is correct
43 Correct 284 ms 153016 KB Output is correct
44 Correct 252 ms 153532 KB Output is correct
45 Correct 259 ms 154808 KB Output is correct
46 Correct 262 ms 116052 KB Output is correct
47 Correct 247 ms 101188 KB Output is correct
48 Correct 295 ms 130400 KB Output is correct
49 Correct 322 ms 131000 KB Output is correct