oj.uz

Submission #728489

# Submission time Handle Problem Language Result Execution time Memory
728489 2023-04-22T14:05:12 Z nguyentunglam Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 168 ms 41628 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[N];
vector<pair<int, int> > query[N];

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);
//        cout << pos << " ";
        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 6 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 9 ms 9904 KB Output is correct
4 Correct 8 ms 9860 KB Output is correct
5 Correct 7 ms 9892 KB Output is correct
6 Correct 9 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9860 KB Output is correct
11 Correct 6 ms 9808 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9908 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 9 ms 9904 KB Output is correct
4 Correct 8 ms 9860 KB Output is correct
5 Correct 7 ms 9892 KB Output is correct
6 Correct 9 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9860 KB Output is correct
11 Correct 6 ms 9808 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9908 KB Output is correct
14 Correct 26 ms 11040 KB Output is correct
15 Correct 53 ms 12240 KB Output is correct
16 Correct 82 ms 13644 KB Output is correct
17 Correct 90 ms 14664 KB Output is correct
18 Correct 77 ms 15632 KB Output is correct
19 Correct 80 ms 15700 KB Output is correct
20 Correct 85 ms 15588 KB Output is correct
21 Correct 83 ms 15556 KB Output is correct
22 Correct 58 ms 14864 KB Output is correct
23 Correct 61 ms 14348 KB Output is correct
24 Correct 73 ms 14220 KB Output is correct
25 Correct 81 ms 15004 KB Output is correct
26 Correct 64 ms 15180 KB Output is correct
27 Correct 69 ms 15608 KB Output is correct
28 Correct 63 ms 15704 KB Output is correct
29 Correct 84 ms 15640 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 9 ms 9904 KB Output is correct
4 Correct 8 ms 9860 KB Output is correct
5 Correct 7 ms 9892 KB Output is correct
6 Correct 9 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9860 KB Output is correct
11 Correct 6 ms 9808 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 6 ms 9908 KB Output is correct
14 Correct 26 ms 11040 KB Output is correct
15 Correct 53 ms 12240 KB Output is correct
16 Correct 82 ms 13644 KB Output is correct
17 Correct 90 ms 14664 KB Output is correct
18 Correct 77 ms 15632 KB Output is correct
19 Correct 80 ms 15700 KB Output is correct
20 Correct 85 ms 15588 KB Output is correct
21 Correct 83 ms 15556 KB Output is correct
22 Correct 58 ms 14864 KB Output is correct
23 Correct 61 ms 14348 KB Output is correct
24 Correct 73 ms 14220 KB Output is correct
25 Correct 81 ms 15004 KB Output is correct
26 Correct 64 ms 15180 KB Output is correct
27 Correct 69 ms 15608 KB Output is correct
28 Correct 63 ms 15704 KB Output is correct
29 Correct 84 ms 15640 KB Output is correct
30 Runtime error 168 ms 41628 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -