oj.uz

Submission #1100890

# Submission time Handle Problem Language Result Execution time Memory
1100890 2024-10-15T01:57:41 Z giaminh2211 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 533 ms 51348 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) begin(x), end(x)

using namespace std;
using ll=long long;
using pii=pair<int, int>;

const int N=2e5+13;
int qr[N];

struct Segtree{
    vector<int> st[N << 2];

    void build(int id, int l, int r){
        if(l==r){
            st[id].push_back(qr[l]);
            return;
        }
        int mid=l+r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid+1, r);
        st[id].resize(st[id << 1].size() + st[id << 1 | 1].size());
        merge(all(st[id << 1]), all(st[id << 1 | 1]), begin(st[id]));
    }

    int get(int id, int l, int r, int u, int v, int x, int y){
        if(l > v || r < u) return 0;
        if(u<=l && r<=v){
            return upper_bound(all(st[id]), y)-lower_bound(all(st[id]), x);
        }
        int mid=l+r >> 1;
        int get1=get(id << 1, l, mid, u, v, x, y);
        int get2=get(id << 1 | 1, mid+1, r, u, v, x, y);
        return get1+get2;
    }

    int walk(int id, int l, int r, int x, int y){
        if(upper_bound(all(st[id]), y) == lower_bound(all(st[id]), x)) return -1;
        if(l==r) return l;
        int mid=l+r >> 1;
        int sus=walk(id << 1 | 1, mid+1, r, x, y);
        if(sus!=-1) return sus;
        return walk(id << 1, l, mid, x, y);
    }
} st;

int n, q;
pii a[N];
bool sus[N];
ll res=0;

void scan(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
        if(a[i].fi > a[i].se){
            swap(a[i].fi, a[i].se);
            sus[i]=1;
        }
    }
    for(int i=1; i<=q; i++){
        cin >> qr[i];
    }
    st.build(1, 1, q);
}

void solve(){
    for(int i=1; i<=n; i++){
        if(a[i].fi == a[i].se){
            res += a[i].fi;
            continue;
        }
        int id=st.walk(1, 1, q, a[i].fi, a[i].se-1);
       // cerr << i << ' ' << id << '\n';
        if(id==-1){
        	int cnt=st.get(1, 1, q, 1, q, a[i].se, 1e9);
        	//cerr << "? " << a[i].se << ' ' << cnt << '\n';
        	cnt%=2;
        	sus[i]^=cnt;
            if(sus[i]) res += a[i].se;
            else res += a[i].fi;
            continue;
        }
        int cnt=st.get(1, 1, q, id+1, q, a[i].se, 1e9);
        if(cnt%2==0){
        	res += a[i].se;
        	//cout << i << ' ' << a[i].se << '\n';
        }
        else{
        	res += a[i].fi;
        	//cout << i << ' ' << a[i].fi << '\n';
        }
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message

fortune_telling2.cpp: In member function 'void Segtree::build(int, int, int)':
fortune_telling2.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid=l+r >> 1;
      |                 ~^~
fortune_telling2.cpp: In member function 'int Segtree::get(int, int, int, int, int, int, int)':
fortune_telling2.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid=l+r >> 1;
      |                 ~^~
fortune_telling2.cpp: In member function 'int Segtree::walk(int, int, int, int, int)':
fortune_telling2.cpp:42:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid=l+r >> 1;
      |                 ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21072 KB Output is correct
2 Correct 4 ms 21072 KB Output is correct
3 Correct 5 ms 21072 KB Output is correct
4 Correct 5 ms 21072 KB Output is correct
5 Correct 6 ms 21072 KB Output is correct
6 Correct 5 ms 21072 KB Output is correct
7 Correct 5 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 5 ms 21072 KB Output is correct
12 Correct 4 ms 21072 KB Output is correct
13 Correct 6 ms 21072 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21072 KB Output is correct
2 Correct 4 ms 21072 KB Output is correct
3 Correct 5 ms 21072 KB Output is correct
4 Correct 5 ms 21072 KB Output is correct
5 Correct 6 ms 21072 KB Output is correct
6 Correct 5 ms 21072 KB Output is correct
7 Correct 5 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 5 ms 21072 KB Output is correct
12 Correct 4 ms 21072 KB Output is correct
13 Correct 6 ms 21072 KB Output is correct
14 Correct 18 ms 22144 KB Output is correct
15 Correct 36 ms 23128 KB Output is correct
16 Correct 54 ms 24104 KB Output is correct
17 Correct 77 ms 25424 KB Output is correct
18 Correct 76 ms 26404 KB Output is correct
19 Correct 76 ms 26464 KB Output is correct
20 Correct 82 ms 26460 KB Output is correct
21 Correct 59 ms 26448 KB Output is correct
22 Correct 32 ms 25940 KB Output is correct
23 Correct 36 ms 25956 KB Output is correct
24 Correct 37 ms 25936 KB Output is correct
25 Correct 34 ms 25936 KB Output is correct
26 Correct 54 ms 26448 KB Output is correct
27 Correct 89 ms 26448 KB Output is correct
28 Correct 59 ms 26448 KB Output is correct
29 Correct 69 ms 26448 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21072 KB Output is correct
2 Correct 4 ms 21072 KB Output is correct
3 Correct 5 ms 21072 KB Output is correct
4 Correct 5 ms 21072 KB Output is correct
5 Correct 6 ms 21072 KB Output is correct
6 Correct 5 ms 21072 KB Output is correct
7 Correct 5 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 5 ms 21072 KB Output is correct
12 Correct 4 ms 21072 KB Output is correct
13 Correct 6 ms 21072 KB Output is correct
14 Correct 18 ms 22144 KB Output is correct
15 Correct 36 ms 23128 KB Output is correct
16 Correct 54 ms 24104 KB Output is correct
17 Correct 77 ms 25424 KB Output is correct
18 Correct 76 ms 26404 KB Output is correct
19 Correct 76 ms 26464 KB Output is correct
20 Correct 82 ms 26460 KB Output is correct
21 Correct 59 ms 26448 KB Output is correct
22 Correct 32 ms 25940 KB Output is correct
23 Correct 36 ms 25956 KB Output is correct
24 Correct 37 ms 25936 KB Output is correct
25 Correct 34 ms 25936 KB Output is correct
26 Correct 54 ms 26448 KB Output is correct
27 Correct 89 ms 26448 KB Output is correct
28 Correct 59 ms 26448 KB Output is correct
29 Correct 69 ms 26448 KB Output is correct
30 Correct 91 ms 47432 KB Output is correct
31 Correct 182 ms 48200 KB Output is correct
32 Correct 320 ms 49084 KB Output is correct
33 Correct 500 ms 51196 KB Output is correct
34 Correct 80 ms 47136 KB Output is correct
35 Correct 505 ms 51336 KB Output is correct
36 Correct 522 ms 51272 KB Output is correct
37 Correct 509 ms 51348 KB Output is correct
38 Correct 485 ms 51196 KB Output is correct
39 Correct 533 ms 51164 KB Output is correct
40 Correct 358 ms 51096 KB Output is correct
41 Correct 482 ms 51200 KB Output is correct
42 Correct 498 ms 51248 KB Output is correct
43 Correct 153 ms 50504 KB Output is correct
44 Correct 149 ms 50448 KB Output is correct
45 Correct 156 ms 50280 KB Output is correct
46 Correct 171 ms 49308 KB Output is correct
47 Correct 233 ms 49044 KB Output is correct
48 Correct 401 ms 51272 KB Output is correct
49 Correct 374 ms 51272 KB Output is correct