oj.uz

Submission #422606

# Submission time Handle Problem Language Result Execution time Memory
422606 2021-06-10T09:02:21 Z ACmachine Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 541 ms 40488 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;
struct segmax{
    vector<int> tree;
    int n;
    segmax(int sz, vector<int> &init){
        n = 1; 
        while(n < sz) n *= 2;
        tree.resize(2 * n, -INF);
        REP(i, n){
            if(i < init.size()){
                tree[i + n] = init[i];
            }
        }
        FORD(i, n - 1, 1, 1){
            tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
        }
    }
    int query(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r){
            return tree[v];
        }
        if(beg >= r || end <= l)
            return -INF;
        int mid = (beg + end) >> 1;
        return max(query(l, r, beg, mid, v << 1), query(l, r, mid, end, v << 1 | 1));
    }
};
// for offline get number of elements > x in segment [l, r];
struct segsum{
    vector<int> tree;
    int n;
    segsum(int sz){
        n = 1; 
        while(n < sz) n *= 2;
        tree.resize(2 * n, 0); 
    }
    int query(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r){
            return tree[v];
        }
        if(beg >= r || end <= l)
            return 0;
        int mid = (beg + end) >> 1;
        return query(l, r, beg, mid, v << 1) + query(l, r, mid, end, v << 1 | 1);
    }
    void upd(int pos, int val){
        pos += n;
        tree[pos] += val;
        for(int i = pos / 2; i > 0; i /= 2){
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
        }
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    const int mx = 700000;
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    vector<int> comp;
    REP(i, n){
        cin >> a[i] >> b[i];        
        comp.pb(a[i]);
        comp.pb(b[i]);
    }
    vector<int> t(k);
    REP(i, k){
        cin >> t[i];
        comp.pb(t[i]);
    }
    vector<int> oa = a, ob = b, ot = t; // to get sum later
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    REP(i, n){
        a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
        b[i] = lower_bound(comp.begin(), comp.end(), b[i]) - comp.begin();
    }
    REP(i, k){
        t[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin(); 
    }
    vector<int> numflips(n, 0);
    vector<int> determined_side(n, 0); // which side is it after finding the last one that determines;that is biggest j,so that T[j] >= a && t[j] < b
    vector<int> initmax(mx, -INF);
    REP(i, k){
        initmax[t[i]] = max(initmax[t[i]], i);
    }
    segmax st(mx, initmax);
    
    struct query{
        int x, tl, query_index, sign; 
        bool operator<(query &oth){
            return tie(x, tl, query_index, sign) < tie(oth.x, oth.tl, oth.query_index, sign);
        }
    };
    vector<query> queries;
    REP(i, n){
        int f = a[i], s = b[i];
        if(f > s) swap(f, s);
        int l = -INF, r = mx; // get number of j, to that t[j] >= max(a[i], b[i]) and index > x; go in order of j, add to segsum at t[j]; 
        // [l, r) are based on indices
        if(f != s){
            l = st.query(f, s, 0, st.n, 1);
            if(l != -INF){
                if(f == a[i])
                    determined_side[i] = 1; 
            }
        }
        queries.pb({l, max(a[i], b[i]), i, -1});
        queries.pb({r, max(a[i], b[i]), i, 1});
    }
    segsum ft(mx);
    sort(queries.begin(), queries.end());
    int pp = 0;
    REP(i, t.size() + 1){
        while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
            auto que = queries[pp];
            int ans = ft.query(que.tl, mx, 0, ft.n, 1);
            ans *= que.sign;
            numflips[que.query_index] += ans;
            pp++;
        }
        if(i == (int)t.size()) 
            break;
        ft.upd(t[i], 1);
    }
    ll sum = 0;
    REP(i, n){
        int side = determined_side[i];
        side ^= (numflips[i] % 2);
        if(side == 0) 
            sum += oa[i];
        else
            sum += ob[i];
    }
    cout << sum << "\n";
}

Compilation message

fortune_telling2.cpp: In constructor 'segmax::segmax(int, std::vector<int>&)':
fortune_telling2.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if(i < init.size()){
      |                ~~^~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
fortune_telling2.cpp:6:19: note: in expansion of macro 'FOR'
    6 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
fortune_telling2.cpp:124:5: note: in expansion of macro 'REP'
  124 |     REP(i, t.size() + 1){
      |     ^~~
fortune_telling2.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
      |               ~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19408 KB Output is correct
2 Correct 16 ms 19516 KB Output is correct
3 Correct 18 ms 19532 KB Output is correct
4 Correct 17 ms 19556 KB Output is correct
5 Correct 16 ms 19532 KB Output is correct
6 Correct 19 ms 19524 KB Output is correct
7 Correct 16 ms 19552 KB Output is correct
8 Correct 17 ms 19628 KB Output is correct
9 Correct 18 ms 19532 KB Output is correct
10 Correct 16 ms 19532 KB Output is correct
11 Correct 16 ms 19532 KB Output is correct
12 Correct 16 ms 19548 KB Output is correct
13 Correct 17 ms 19532 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19408 KB Output is correct
2 Correct 16 ms 19516 KB Output is correct
3 Correct 18 ms 19532 KB Output is correct
4 Correct 17 ms 19556 KB Output is correct
5 Correct 16 ms 19532 KB Output is correct
6 Correct 19 ms 19524 KB Output is correct
7 Correct 16 ms 19552 KB Output is correct
8 Correct 17 ms 19628 KB Output is correct
9 Correct 18 ms 19532 KB Output is correct
10 Correct 16 ms 19532 KB Output is correct
11 Correct 16 ms 19532 KB Output is correct
12 Correct 16 ms 19548 KB Output is correct
13 Correct 17 ms 19532 KB Output is correct
14 Correct 36 ms 20624 KB Output is correct
15 Correct 58 ms 21576 KB Output is correct
16 Correct 80 ms 22712 KB Output is correct
17 Correct 109 ms 23764 KB Output is correct
18 Correct 102 ms 23764 KB Output is correct
19 Correct 101 ms 23756 KB Output is correct
20 Correct 107 ms 23764 KB Output is correct
21 Correct 116 ms 23728 KB Output is correct
22 Correct 82 ms 23232 KB Output is correct
23 Correct 82 ms 23288 KB Output is correct
24 Correct 79 ms 23156 KB Output is correct
25 Correct 81 ms 23360 KB Output is correct
26 Correct 87 ms 23096 KB Output is correct
27 Correct 97 ms 23676 KB Output is correct
28 Correct 87 ms 23768 KB Output is correct
29 Correct 105 ms 23744 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19408 KB Output is correct
2 Correct 16 ms 19516 KB Output is correct
3 Correct 18 ms 19532 KB Output is correct
4 Correct 17 ms 19556 KB Output is correct
5 Correct 16 ms 19532 KB Output is correct
6 Correct 19 ms 19524 KB Output is correct
7 Correct 16 ms 19552 KB Output is correct
8 Correct 17 ms 19628 KB Output is correct
9 Correct 18 ms 19532 KB Output is correct
10 Correct 16 ms 19532 KB Output is correct
11 Correct 16 ms 19532 KB Output is correct
12 Correct 16 ms 19548 KB Output is correct
13 Correct 17 ms 19532 KB Output is correct
14 Correct 36 ms 20624 KB Output is correct
15 Correct 58 ms 21576 KB Output is correct
16 Correct 80 ms 22712 KB Output is correct
17 Correct 109 ms 23764 KB Output is correct
18 Correct 102 ms 23764 KB Output is correct
19 Correct 101 ms 23756 KB Output is correct
20 Correct 107 ms 23764 KB Output is correct
21 Correct 116 ms 23728 KB Output is correct
22 Correct 82 ms 23232 KB Output is correct
23 Correct 82 ms 23288 KB Output is correct
24 Correct 79 ms 23156 KB Output is correct
25 Correct 81 ms 23360 KB Output is correct
26 Correct 87 ms 23096 KB Output is correct
27 Correct 97 ms 23676 KB Output is correct
28 Correct 87 ms 23768 KB Output is correct
29 Correct 105 ms 23744 KB Output is correct
30 Correct 125 ms 24992 KB Output is correct
31 Correct 204 ms 28088 KB Output is correct
32 Correct 302 ms 32056 KB Output is correct
33 Correct 529 ms 40368 KB Output is correct
34 Correct 105 ms 23916 KB Output is correct
35 Correct 520 ms 40328 KB Output is correct
36 Correct 541 ms 40340 KB Output is correct
37 Correct 531 ms 40284 KB Output is correct
38 Correct 517 ms 40268 KB Output is correct
39 Correct 521 ms 40356 KB Output is correct
40 Correct 518 ms 40092 KB Output is correct
41 Correct 541 ms 40356 KB Output is correct
42 Correct 513 ms 40228 KB Output is correct
43 Correct 369 ms 39764 KB Output is correct
44 Correct 375 ms 39660 KB Output is correct
45 Correct 414 ms 39740 KB Output is correct
46 Correct 373 ms 38432 KB Output is correct
47 Correct 353 ms 38176 KB Output is correct
48 Correct 438 ms 40376 KB Output is correct
49 Correct 422 ms 40488 KB Output is correct