Submission #1216847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216847		Malix	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	375 ms	76156 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,q,m,k;
unordered_map<int,int> mp;
vi a,b,arr,c,ft;
vector<ti> A;
vii mx;

void update(int x){
    x++;
    while(x<=q){
        ft[x]++;
        x+=LSOne(x);
    }
}

int query(int x){
    x++;
    int ans=0;
    while(x){
        ans+=ft[x];
        x-=LSOne(x);
    }
    return ans;
}

int main() {   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    a.resize(n);b.resize(n);A.resize(n);
    REP(i,0,n){
        cin>>a[i]>>b[i];
        arr.PB(a[i]);
        arr.PB(b[i]);
    }
    sort(all(arr));
    arr.erase(unique(all(arr)),arr.end());
    m=arr.size();
    k=log2(m)+1;
    REP(i,0,m)mp[arr[i]]=i;
    mx.resize(m,vi(k,-1));
    c.resize(q,-1);
    REP(i,0,q){
        int x;cin>>x;
        auto it=upper_bound(all(arr),x);
        if(it==arr.begin())continue;
        it--;
        int ps=it-arr.begin();
        c[i]=ps;
        mx[ps][0]=i;
    }
    REP(i,0,n)a[i]=mp[a[i]];
    REP(i,0,n)b[i]=mp[b[i]];
    REP(i,0,n)A[i]={max(a[i],b[i]),min(a[i],b[i]),i};
    sort(all(A));reverse(all(A));
    ft.resize(q+1,0);
    REP(j,1,k)REP(i,0,m)if(i+(1<<(j-1))<m)mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    ll ans=0;
    priority_queue<pi> pq;
    REP(i,0,q)pq.push({c[i],i});
    REP(i,0,n){
        auto [x,y,z]=A[i];
        swap(x,y);
        int t=y-1;
        int pos=-1;
        if(y>x){
            int dif=0;
            if(t!=x)dif=log2(t-x);
            pos=max(mx[x][dif],mx[t-(1<<dif)+1][dif]);
        }
        while(!pq.empty()&&pq.top().F>=y){
            update(pq.top().S);
            pq.pop();
        }
        int cnt=query(q-1)-query(pos);
        if(pos==-1){
            if(cnt%2==0)ans+=(ll)arr[a[z]];
            else ans+=(ll)arr[b[z]];
        }
        else{
            if(cnt%2==0)ans+=(ll)arr[y];
            else ans+=(ll)arr[x];
        }
    }
    cout<<ans;
}

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