Submission #1271644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271644		nquang	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	267 ms	58328 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define task "fortunetelling2"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define lwb lower_bound
#define upb upper_bound
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const int maxn = 2e5;
const int MAX = 6e5;
int n,k;
int a[maxn+5],b[maxn+5];
int t[maxn+5];
int f[MAX+5][21];
int maxk;
int last[maxn+5];
int ord[maxn+5];
int bit[MAX+5];
int tmp[MAX+5];
int id=0;
void init(){
    rep(i,1,id) bit[i]=0;
}
void upd(int u,int val){
    while(u>0){
        bit[u]+=val;
        u-=u&(-u);
    }
}
int getSuf(int u){
    int res=0;
    while(u<=id){
        res+=bit[u];
        u+=u&(-u);
    }
    return res;
}
int getMax(int u,int v){
    int k=log2(v-u+1);
    return max(f[u][k],f[v-(1<<k)+1][k]);
}
bool cmp(int u,int v){
    return last[u]>last[v];
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    rep(i,1,n) cin >> a[i] >> b[i];
    rep(i,1,k) cin >> t[i];
    rep(i,1,n){
        tmp[++id]=a[i];
        tmp[++id]=b[i];
    }
    rep(i,1,k) tmp[++id]=t[i];
    sort(tmp+1,tmp+id+1);
    rep(i,1,n){
        a[i]=lwb(tmp+1,tmp+id+1,a[i])-tmp;
        b[i]=lwb(tmp+1,tmp+id+1,b[i])-tmp;
    }
    rep(i,1,k){
        t[i]=lwb(tmp+1,tmp+id+1,t[i])-tmp;
        f[t[i]][0]=max(f[t[i]][0],i);
    }
    maxk = log2(id);
    rep(k,1,maxk){
        rep(i,1,id-(1<<k)+1){
            f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
        }
    }
    rep(i,1,n){
        if(a[i]==b[i]) last[i]=0;
        else last[i]=getMax(min(a[i],b[i]),max(a[i],b[i])-1);
    }
    rep(i,1,n) ord[i]=i;
    sort(ord+1,ord+n+1,cmp);
    init();
    int cur=k;
    ll ans=0;
    rep(i,1,n){
        int u=ord[i];
        while(cur>last[u]){
            upd(t[cur],1);
            --cur;
        }
        if(last[u]>0){
            if(a[u]<b[u]) swap(a[u],b[u]);
        }
        if(getSuf(max(a[u],b[u]))%2) swap(a[u],b[u]);
        ans+=tmp[a[u]];
    }
    cout << ans;
    return 0;
}

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