Submission #852011

#TimeUsernameProblemLanguageResultExecution timeMemory
852011MrM7mdBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
146 ms100808 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' // #define int long long #define F first #define S second #define pb push_back #define all(a) a.begin(),a.end() const int N=2e5 + 3; const int MOD=1e9+7; const int off=(1<<21); int t[off*2],dis[off*2],lazy[off*2]; void upd2(int x,int v){ x+=off; t[x]+=v; while(x/=2){ t[x]=t[x*2]+t[x*2+1]; } } int get2(int x,int l,int r,int st,int en){ if(r<st||l>en)return 0; if(r<=en&&l>=st){ return t[x]; } int md=(l+r)/2; return get2(x*2,l,md,st,en)+get2(x*2+1,md+1,r,st,en); } void push(int x,int l,int r){ if(lazy[x]==0)return; if(l!=r){ lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x]; } dis[x]+=lazy[x]; lazy[x]=0; } void upd(int x,int l,int r,int st,int en,int df){ push(x,l,r); if(r<st||l>en)return ; if(l>=st&&r<=en){ lazy[x]+=df; push(x,l,r); return ; } int md=(l+r)/2; upd(x*2,l,md,st,en,df); upd(x*2+1,md+1,r,st,en,df); dis[x]=max(dis[x*2],dis[x*2+1]); } int get(int x,int l,int r,int st,int en){ push(x,l,r); if(r<st||l>en)return INT_MIN; if(l>=st&&r<=en){ return dis[x]; } int md=(l+r)/2; int ll=get(x*2,l,md,st,en); int rr=get(x*2+1,md+1,r,st,en); return max(ll,rr); } std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){ for(int i=0;i<off*2;i++)dis[i]=INT_MIN,t[i]=0,lazy[i]=0; int q=X.size(),n=A.size(); vector<int>ans; set<int>st; for(auto it:A)st.insert(it); for(auto it:V)st.insert(it); int cnt=1; map<int,int>mp; for(auto it:st)mp[it]=cnt++; vector<set<int>>vv(1e6+20); for(int i=0;i<n;i++){ int a=A[i]; upd2(mp[a],1); vv[mp[a]].insert(i+1); } int cur=0; for(int i=1;i<=cnt;i++){ if(vv[i].empty()){ continue; } cur+=vv[i].size(); upd(1,1,off-1,i+1,i+1,(-1*dis[i+off])+(*vv[i].rbegin())-cur); } for(int j=0;j<q;j++){ int x=X[j],v=mp[V[j]]; int a=mp[A[x]],prev; if(a<v){ upd(1,1,off-1,a+2,v,1); } else if( a>v){ upd(1,1,off-1,v+1,a+1,-1); } upd(1,1,off-1,a+1,a+1,-1*dis[a+off]); upd2(a,-1); vv[a].erase(x+1); vv[v].insert(x+1); upd2(v,1); prev=get2(1,1,off-1,1,v+1); upd(1,1,off-1,v+1,v+1,(-1*dis[v+off])+(*vv[v].rbegin())-prev); if(vv[a].size()&&a!=v){ prev=get2(1,1,off-1,1,a+1); upd(1,1,off-1,a+1,a+1,(*vv[a].rbegin())-prev); } A[x]=V[j]; ans.pb(dis[1]); } return ans; } /* 1 2 5 7 3 5 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...