oj.uz

Submission #728490

# Submission time Handle Problem Language Result Execution time Memory
728490 2023-04-22T14:06:38 Z nguyentunglam Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 546 ms 59792 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 2e5 + 10, M = 6e5;
int a[N], b[N], c[N], T[M * 4 + 10], bit[N], ans[N];
int n, m;
vector<int> rrh, lst[M + 10];
vector<pair<int, int> > query[M + 10];

int id(int x) {
    return upper_bound(rrh.begin(), rrh.end(), x) - rrh.begin();
}

void up(int s, int l, int r, int pos, int val) {
    if (l == r) {
        T[s] = max(T[s], val);
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid) up(s << 1, l, mid, pos, val);
    else up(s << 1 | 1, mid + 1, r, pos, val);
    T[s] = max(T[s << 1], T[s << 1 | 1]);
}

int get(int s, int l, int r, int from, int to) {
    if (l > to || r < from) return 0;
    if (from <= l && r <= to) return T[s];
    int mid = l + r >> 1;
    return max(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}

void upbit(int pos, int val) {
    while (pos) {
        bit[pos] += val;
        pos -= pos & -pos;
    }
}

int getbit(int pos) {
    int ret = 0;
    while (pos <= m) {
        ret += bit[pos];
        pos += pos & -pos;
    }
    return ret;
}

int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        rrh.push_back(a[i]);
        rrh.push_back(b[i]);
    }
    for(int i = 1; i <= m; i++) {
        cin >> c[i];
        rrh.push_back(c[i]);
    }

    sort(rrh.begin(), rrh.end());
    rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
    int sz = rrh.size();

    for(int i = 1; i <= m; i++) {
        lst[id(c[i])].push_back(i);
        up(1, 1, sz, id(c[i]), i);
    }

    for(int i = 1; i <= n; i++) {
        int pos = get(1, 1, sz, id(min(a[i], b[i])), id(max(a[i], b[i])) - 1);
        if (pos && a[i] < b[i]) ans[i] = 1;
        query[id(max(a[i], b[i]))].emplace_back(pos + 1, i);
    }

    for(int i = sz; i >= 1; i--) {
        for(int &j : lst[i]) upbit(j, 1);

        for(auto &it : query[i]) {
            int pos, idx; tie(pos, idx) = it;
            ans[idx] += getbit(pos);
        }
    }
    long long res = 0;
    for(int i = 1; i <= n; i++) {
        if (ans[i] % 2) res += b[i];
        else res += a[i];
    }
    cout << res;
}

Compilation message

fortune_telling2.cpp: In function 'void up(int, int, int, int, int)':
fortune_telling2.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int, int)':
fortune_telling2.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:56:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:60:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28612 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28676 KB Output is correct
4 Correct 17 ms 28628 KB Output is correct
5 Correct 17 ms 28672 KB Output is correct
6 Correct 17 ms 28628 KB Output is correct
7 Correct 15 ms 28668 KB Output is correct
8 Correct 15 ms 28628 KB Output is correct
9 Correct 16 ms 28572 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 15 ms 28540 KB Output is correct
12 Correct 14 ms 28548 KB Output is correct
13 Correct 16 ms 28628 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28612 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28676 KB Output is correct
4 Correct 17 ms 28628 KB Output is correct
5 Correct 17 ms 28672 KB Output is correct
6 Correct 17 ms 28628 KB Output is correct
7 Correct 15 ms 28668 KB Output is correct
8 Correct 15 ms 28628 KB Output is correct
9 Correct 16 ms 28572 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 15 ms 28540 KB Output is correct
12 Correct 14 ms 28548 KB Output is correct
13 Correct 16 ms 28628 KB Output is correct
14 Correct 38 ms 29716 KB Output is correct
15 Correct 55 ms 30892 KB Output is correct
16 Correct 76 ms 32300 KB Output is correct
17 Correct 93 ms 33224 KB Output is correct
18 Correct 90 ms 33320 KB Output is correct
19 Correct 85 ms 33228 KB Output is correct
20 Correct 86 ms 33260 KB Output is correct
21 Correct 83 ms 33312 KB Output is correct
22 Correct 68 ms 32936 KB Output is correct
23 Correct 77 ms 32424 KB Output is correct
24 Correct 61 ms 32292 KB Output is correct
25 Correct 71 ms 33076 KB Output is correct
26 Correct 69 ms 32912 KB Output is correct
27 Correct 89 ms 33312 KB Output is correct
28 Correct 80 ms 33224 KB Output is correct
29 Correct 77 ms 33228 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28612 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28676 KB Output is correct
4 Correct 17 ms 28628 KB Output is correct
5 Correct 17 ms 28672 KB Output is correct
6 Correct 17 ms 28628 KB Output is correct
7 Correct 15 ms 28668 KB Output is correct
8 Correct 15 ms 28628 KB Output is correct
9 Correct 16 ms 28572 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 15 ms 28540 KB Output is correct
12 Correct 14 ms 28548 KB Output is correct
13 Correct 16 ms 28628 KB Output is correct
14 Correct 38 ms 29716 KB Output is correct
15 Correct 55 ms 30892 KB Output is correct
16 Correct 76 ms 32300 KB Output is correct
17 Correct 93 ms 33224 KB Output is correct
18 Correct 90 ms 33320 KB Output is correct
19 Correct 85 ms 33228 KB Output is correct
20 Correct 86 ms 33260 KB Output is correct
21 Correct 83 ms 33312 KB Output is correct
22 Correct 68 ms 32936 KB Output is correct
23 Correct 77 ms 32424 KB Output is correct
24 Correct 61 ms 32292 KB Output is correct
25 Correct 71 ms 33076 KB Output is correct
26 Correct 69 ms 32912 KB Output is correct
27 Correct 89 ms 33312 KB Output is correct
28 Correct 80 ms 33224 KB Output is correct
29 Correct 77 ms 33228 KB Output is correct
30 Correct 196 ms 39688 KB Output is correct
31 Correct 284 ms 46572 KB Output is correct
32 Correct 360 ms 50096 KB Output is correct
33 Correct 546 ms 59740 KB Output is correct
34 Correct 172 ms 41104 KB Output is correct
35 Correct 535 ms 59660 KB Output is correct
36 Correct 544 ms 59792 KB Output is correct
37 Correct 533 ms 59648 KB Output is correct
38 Correct 523 ms 59720 KB Output is correct
39 Correct 540 ms 59716 KB Output is correct
40 Correct 506 ms 59744 KB Output is correct
41 Correct 522 ms 59704 KB Output is correct
42 Correct 530 ms 59684 KB Output is correct
43 Correct 342 ms 55520 KB Output is correct
44 Correct 362 ms 56020 KB Output is correct
45 Correct 336 ms 56920 KB Output is correct
46 Correct 360 ms 53560 KB Output is correct
47 Correct 314 ms 50768 KB Output is correct
48 Correct 441 ms 55660 KB Output is correct
49 Correct 465 ms 55696 KB Output is correct