Submission #1219002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219002		Sofiatpc	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	0 ms	320 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 2*1e5+5;
pair<int,int> p[MAXN], t[MAXN];
int mx[MAXN*4], id[MAXN], bit[MAXN], k;

bool cmp(pair<int,int> a, pair<int,int> b){return max(a.fi,a.sc) < max(b.fi,b.sc);}

void update(int node, int l, int r, int i, int x){
    if(i < l || r < i)return;
    if(l == r){
        mx[node] = x;
        return;
    }

    int mid = (l+r)/2 , e = node*2, d = node*2+1;
    update(e,l,mid,i,x); update(d,mid+1,r,i,x);
    mx[node] = max(mx[e], mx[d]);
}

int bb(int node, int l, int r, int x){
    if(l == r){
        if(mx[node] < x)return -1;
        return l;
    }

    int mid = (l+r)/2 , e = node*2, d = node*2+1;
    if(mx[d] >= x)return bb(d,mid+1,r,x);
    return bb(e,l,mid,x);
}

void updateB(int i, int x){
    for(; i <= k; i += i&-i)
        bit[i] += x;
}

int queryB(int i){
    if(i < 1)return 0;
    int ans = 0;
    for(; i > 0; i -= i&-i)
        ans += bit[i];
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>p[i].fi>>p[i].sc;

    sort(p+1,p+1+n, cmp);

    for(int i = 1; i <= k; i++){
        cin>>t[i].fi;
        t[i].sc = i;
    }

    sort(t+1,t+1+k);

    int cur = 1;
    for(int i = 1; i <= k; i++){
        while(cur <= n && max(p[cur].fi,p[cur].sc) <= t[i].fi){
            id[cur] = bb(1,1,k, min(p[cur].fi,p[cur].sc));
            cur++;
        }

        update(1,1,k, t[i].sc, t[i].fi);
    }
    while(cur <= n){
        id[cur] = bb(1,1,k, min(p[cur].fi,p[cur].sc));
        cur++;
    }

    cur = n;
    int ans = 0;
    for(int i = k; i >= 1; i--){
        while(cur > 0 && max(p[cur].fi,p[cur].sc) > t[i].fi){
            int x = queryB(k) - queryB(id[cur]);
            if(id[cur] == -1){
                if(x%2 == 0)ans += p[cur].fi;
                else ans += p[cur].sc;
            }else{
                if(x%2 == 0)ans += max(p[cur].fi, p[cur].sc);
                else ans += min(p[cur].fi, p[cur].sc);
            }


            cur--;
        }

        updateB(t[i].sc, 1);
    }
    while(cur > 0){
        int x = queryB(k) - queryB(id[cur]);
        if(id[cur] == -1){
            if(x%2 == 0)ans += p[cur].fi;
            else ans += p[cur].sc;
        }else{
            if(x%2 == 0)ans += max(p[cur].fi, p[cur].sc);
            else ans += min(p[cur].fi, p[cur].sc);
        }

        cur--;
    }

    cout<<ans<<"\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65