Submission #1100890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100890		giaminh2211	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	533 ms	51348 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65