Submission #236696

#TimeUsernameProblemLanguageResultExecution timeMemory
236696LyestriaFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
814 ms55356 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mn=2e5+10; int a[mn],b[mn],si[mn],v[mn]; vector<int>seg[mn*4]; #define mid ((l+r)>>1) void init(int x,int l,int r){ for(int i=l;i<=r;i++)seg[x].push_back(v[i]); sort(seg[x].begin(),seg[x].end()); if(l!=r){ init(x*2,l,mid); init(x*2+1,mid+1,r); } } int numg(vector<int>&v,int x){ return v.size()-(lower_bound(v.begin(),v.end(),x)-v.begin()); } int query1(int x,int l,int r,int a,int b){ if(l==r){ assert(seg[x].size()==1); if(a<=seg[x][0]&&seg[x][0]<b)return l; else return l-1; } else{ if(numg(seg[x*2+1],a)-numg(seg[x*2+1],b))return query1(x*2+1,mid+1,r,a,b); else return query1(x*2,l,mid,a,b); } } int num(int x,int l,int r,int a,int b,int c){ if(l==a&&r==b)return numg(seg[x],c); if(b<=mid)return num(x*2,l,mid,a,b,c); else if(a>mid)return num(x*2+1,mid+1,r,a,b,c); else return num(x*2,l,mid,a,mid,c)+num(x*2+1,mid+1,r,mid+1,b,c); } int main(){ cin.tie(0); cin.sync_with_stdio(0); int n,k; cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; if(a[i]>b[i]){ swap(a[i],b[i]); si[i]=1; } } for(int i=1;i<=k;i++){ cin>>v[i]; } init(1,1,k); ll ans=0; for(int i=0;i<n;i++){ int t=query1(1,1,k,a[i],b[i]); if(t)si[i]=1; if(t<k)si[i]+=num(1,1,k,t+1,k,a[i]); if(si[i]&1)ans+=b[i]; else ans+=a[i]; } printf("%lld",ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...