Submission #52797

#	Time	Username	Problem	Language	Result	Execution time	Memory
52797		Smelskiy	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	264 ms	106376 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;


int n,m;
pair<int,int> a[200005];
pair<int,int> b[200005];
int t[3000005];
int tt[3000005];
long long ans;
int x,y;
int pos;
int xx;
int sz;

inline bool cmp(pair<int,int> x,pair<int,int> y) {
    return max(x.first,x.second)<max(y.first,y.second);
}


inline void update(int x,int y) {
    x+=sz-1;
    t[x]++;
    tt[x]=y;
    x>>=1;
    while (x) {
        t[x]=t[x+x]+t[x+x+1];
        tt[x]=max(tt[x+x],tt[x+x+1]);
        x>>=1;
    }
}

int get_pos(int l,int r,int x,int y) {
    if (tt[x]<y) return 0;
    if (l==r) return l;
    int mid=(l+r)>>1;
    int res=get_pos(mid+1,r,x+x+1,y);
    if (!res) res=get_pos(l,mid,x+x,y);
    return res;
}

int get_cnt(int l,int r,int ll,int rr,int x) {
    if (l>r || ll>r || l>rr || ll>rr) return 0;
    if (l>=ll && r<=rr) return t[x];
    int mid=(l+r)>>1;
    return get_cnt(l,mid,ll,rr,x+x)+get_cnt(mid+1,r,ll,rr,x+x+1);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=m;++i) {
        cin>>b[i].first;
        b[i].second=i;
    }
    sort(b+1,b+m+1);
    int last=1;
    sz=1;
    bool z=false;
    while (sz<m) sz+=sz;
    for (int i=1;i<=n;++i) {
        x=max(a[i].first,a[i].second);
        y=min(a[i].first,a[i].second);
        if (x==y) {
            ans+=x;
            continue;
        }
        while (last<=m && b[last].first<x) {
            update(b[last].second,b[last].first);
            ++last;
        }
        pos=get_pos(1,sz,1,y);
        if (pos) z=true;
        else z=false;
        ++pos;
        xx=get_cnt(1,sz,pos,m,1);
//        cout<<x<<" "<<y<<" "<<pos<<" "<<xx<<'\n';
        xx=m-pos+1-xx;
        xx%=2;
        if (z) {
            if (xx) ans+=y;
            else ans+=x;
        } else {
            if (xx) ans+=a[i].second;
            else ans+=a[i].first;
        }
    }
    cout<<ans;
}

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