Submission #786746

#TimeUsernameProblemLanguageResultExecution timeMemory
786746winter0101Fortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
778 ms68480 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) using pii=pair<int,int>; using pli=pair<long long,int>; using pil=pair<int,long long>; using pll=pair<long long,long long>; const int maxn=2e5+9; int st[maxn*4*3]; void update(int id,int l,int r,int u,int val){ if (l>u||r<u)return; if (l==r){ st[id]=val; return; } int mid=(l+r)/2; update(id*2,l,mid,u,val); update(id*2+1,mid+1,r,u,val); st[id]=max(st[id*2],st[id*2+1]); } int get(int id,int l,int r,int u,int v){ if (l>v||r<u||u>v)return 0; if (u<=l&&r<=v)return st[id]; int mid=(l+r)/2; return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v)); } int m; int bit[maxn*3]; void add(int pos,int val){ for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val; } int get(int pos){ if (pos==0)return 0; int sum=0; for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos]; return sum; } int a[maxn*3],b[maxn*3]; int c[maxn*3]; bool flip[maxn*3]; int d[maxn*3]; int ren[maxn*3]; vector<int>query[maxn*3]; signed main(){ srand(time(0)); ios_base::sync_with_stdio(0); cin.tie(0); //freopen("usaco.INP","r",stdin); //freopen("usaco.OUT","w",stdout); int n,q; cin>>n>>q; vector<int>num; num.pb(0); for1(i,1,n){ cin>>a[i]>>b[i]; num.pb(a[i]); num.pb(b[i]); } for1(i,1,q){ cin>>c[i]; num.pb(c[i]); } sort(all(num)); map<int,int>nen; m=0; for1(i,1,sz(num)-1){ if (num[i]>num[i-1]){ nen[num[i]]=nen[num[i-1]]+1; m=nen[num[i]]; ren[m]=num[i]; } } for1(i,1,n){ a[i]=nen[a[i]]; b[i]=nen[b[i]]; } for1(i,1,q)c[i]=nen[c[i]]; for1(i,1,q){ update(1,1,m,c[i],i); } for1(i,1,n){ int x=min(a[i],b[i]),y=max(a[i],b[i]); int vcl=get(1,1,m,x,y-1); if (vcl==0){ continue; } query[vcl].pb(i); if (a[i]<b[i]){ flip[i]=1; } } for1(i,1,q){ add(c[i],1); for (auto v:query[i]){ d[v]=-get(m)+get(max(a[v],b[v])-1); } } long long sum=0; for1(i,1,n){ d[i]+=get(m)-get(max(a[i],b[i])-1); d[i]%=2; flip[i]^=d[i]; if (!flip[i]){ sum+=ren[a[i]]; } else sum+=ren[b[i]]; } cout<<sum; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...