Submission #1216843

#TimeUsernameProblemLanguageResultExecution timeMemory
1216843MalixFortune Telling 2 (JOI14_fortune_telling2)C++20
0 / 100
1 ms320 KiB
#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<=m){ 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(m+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(m-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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...