Submission #1100921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100921		sitablechair	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	423 ms	79808 KiB

fortune_telling2

#include<bits/stdc++.h>
#define ll long long
#define sz(x) (signed)x.size()
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,l,r) for(int i=r;i>=l;i--)
#define F "CHOTMH"
#define fio freopen(F".inp","r",stdin);freopen(F".out","w",stdout);
using namespace std;

int n,k;

const int N=6e5+3;

struct BIT {
    int pf[N];
    void upd(int u,int val) {
        while(u<=k) {
            pf[u]=pf[u]+val;
            u+=u&(-u);
        }
    }
    int query(int u) {
        int ans=0;
        while(u>0) {
            ans+=pf[u];
            u-=u&(-u);
        }
        return ans;
    }
};
struct BITT {
    int pf[N];
    void upd(int u,int val) {
        while(u<=k) {
            pf[u]=min(pf[u],val);
            u+=u&(-u);
        }
    }
    int query(int u) {
        int ans=2e9;
        while(u>0) {
            ans=min(pf[u],ans);
            u-=u&(-u);
        }
        return ans;
    }
};
BIT bit;
BITT sus;
vector<int> in[N],sigma[N],sigma1[N],big;
pair<int,int> a[N];
bool huhu[N];
int q[N],pf[N],pp[N];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    //fio
    cin >> n >> k;
    ll ans=0;
    For(i,1,n) {
        cin >> a[i].ff >> a[i].ss;
        big.pb(a[i].ff);
        big.pb(a[i].ss);
    }
    For(i,1,k) {
        bit.pf[i]=0;
        sus.pf[i]=2e9;
        cin >> q[i];
        big.pb(q[i]);
        pf[i]=max(pf[i-1],q[i]);
    }
    sort(big.begin(),big.end());
    big.resize(unique(big.begin(),big.end())-big.begin());
    For(i,1,k) {
        int ind=lower_bound(big.begin(),big.end(),q[i])-big.begin();
        in[ind+1].pb(i);
    }
    For(i,1,n) {
        int ind=lower_bound(big.begin(),big.end(),a[i].ff)-big.begin();
        int ind1=lower_bound(big.begin(),big.end(),a[i].ss)-big.begin();
        if (a[i].ff!=a[i].ss) {
            sigma[min(ind,ind1)+1].pb(i);
            sigma1[max(ind,ind1)+1].pb(i);
        }
        else ans+=a[i].ff,huhu[i]=1;
    }
    ForD(i,1,sz(big)) {
        for(auto el: in[i]) sus.upd(k-el+1,q[el]);
        for(auto el: sigma[i]) {
            int l=(a[el].ff<a[el].ss?(lower_bound(pf+1,pf+1+k,a[el].ff)-pf)+1:1),r=k;
            int cc=l;
            if (l>k+1) {
                ans+=a[el].ff;
                huhu[el]=1;
            }
            if (a[el].ff<a[el].ss) swap(a[el].ff,a[el].ss);
            while(l<r) {
                int mid=l+(r-l+1)/2;
                if (sus.query(k-mid+1)<a[el].ff) l=mid;
                else r=mid-1;
            }
            if (sus.query(k-l+1)<a[el].ff) pp[el]=l;
            else pp[el]=cc;
        }
    }
    ForD(i,1,sz(big)) {
        for(auto el: in[i]) bit.upd(el,1);
        for(auto el: sigma1[i]) {
            if (huhu[el]) continue;
            int tm=bit.query(k)-bit.query(pp[el]-1);
            if (tm%2) ans+=a[el].ss;
            else ans+=a[el].ff;
        }
    }
    cout << ans << endl;
    return 0;
}

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