Submission #445800

#TimeUsernameProblemLanguageResultExecution timeMemory
445800julian33Bubble Sort 2 (JOI18_bubblesort2)C++14
0 / 100
21 ms3660 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=1e6+5; //make sure this is right const int mod=1e9+7; struct node{ int lft,rt; }; node st[4*mxN]; int a[mxN],lazy[4*mxN],cnt[mxN]; vector<int> all; int get(int x){ int f=lower_bound(all.begin(),all.begin(),x)-all.begin()+1; return f+(cnt[f]++); } void pushup(int v){ st[v].lft=max(st[v<<1].lft,st[v<<1|1].lft); st[v].rt=max(st[v<<1].rt,st[v<<1|1].rt); } void prop(int v,int val){ if(val<0){ int tmp=st[v].rt; st[v].rt=max(0,st[v].rt+val); val=min(0,val+tmp); st[v].lft+=abs(val); } else{ int tmp=st[v].lft; st[v].lft=max(0,st[v].lft-val); val=max(0,val-tmp); st[v].rt+=val; } } void push(int v){ lazy[v<<1]+=lazy[v]; lazy[v<<1|1]+=lazy[v]; prop(v<<1,lazy[v]); prop(v<<1|1,lazy[v]); lazy[v]=0; } void point_upd(int v,int l,int r,int ind,int val){ if(ind<l || ind>r) return; if(l==r){ if(val<0){ st[v].rt=0; st[v].lft=abs(val); } else{ st[v].lft=0; st[v].rt=val; } } else{ int m=(l+r)>>1; push(v); point_upd(v<<1,l,m,ind,val); point_upd(v<<1|1,m+1,r,ind,val); pushup(v); } } void range_upd(int v,int l,int r,int lq,int rq,int val){ if(lq>rq) return; if(l>=lq && r<=rq){ prop(v,val); lazy[v]+=val; } else{ int m=(l+r)>>1; push(v); range_upd(v<<1,l,m,lq,min(m,rq),val); range_upd(v<<1|1,m+1,r,max(lq,m+1),rq,val); pushup(v); } } struct BIT{ ll bit[mxN]; void upd(int x,int v){while(x<mxN){bit[x]+=v;x+=x&-x;}} ll sum(int x){ll res=0;while(x){res+=bit[x];x-=x&-x;}return res;} }; BIT bit; vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){ int n=sz(A); int q=sz(X); for(int &i:A) all.pb(i); for(int &i:V) all.pb(i); sort(all.begin(),all.end()); all.resize(unique(all.begin(),all.end())-all.begin()); vector<int> ans; for(int i=0;i<n;i++){ A[i]=get(A[i]); bit.upd(A[i],1); } for(int i=0;i<n;i++){ int s=bit.sum(A[i]); int move=s-i-1; point_upd(1,1,n,A[i],move); } for(int i=0;i<q;i++){ V[i]=get(V[i]); bit.upd(A[X[i]],-1); point_upd(1,1,n,A[X[i]],0); int f=A[X[i]]; int s=V[i]; bit.upd(s,1); int su=bit.sum(s); int move=su-X[i]-1; point_upd(1,1,n,s,move); if(f<s){ range_upd(1,1,n,f+1,s-1,-1); } else{ range_upd(1,1,n,s+1,f-1,1); } ans.pb(max(st[1].lft,st[1].rt)); A[X[i]]=s; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...