Submission #445808

#TimeUsernameProblemLanguageResultExecution timeMemory
445808julian33Bubble Sort 2 (JOI18_bubblesort2)C++14
0 / 100
24 ms1884 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; int st[4*mxN]; int a[mxN],lazy[4*mxN]; vector<pii> all; int get(pii x){ return lower_bound(all.begin(),all.end(),x)-all.begin()+1; } void push(int v){ lazy[v<<1]+=lazy[v]; lazy[v<<1|1]+=lazy[v]; st[v<<1]+=lazy[v]; st[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){ st[v]=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); st[v]=max(st[v<<1],st[v<<1|1]); } } void range_upd(int v,int l,int r,int lq,int rq,int val){ if(lq>rq) return; if(l>=lq && r<=rq){ st[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); st[v]=max(st[v<<1],st[v<<1|1]); } } 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=0;i<n;i++){ all.pb({A[i],i}); } for(int i=0;i<q;i++){ all.pb({V[i],X[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],i}); bit.upd(A[i],1); } for(int i=0;i<n;i++){ int sm=bit.sum(A[i]); int move=sm-i-1; point_upd(1,1,2*n,A[i],move); } for(int i=0;i<q;i++){ int f=A[X[i]]; int s=get({V[i],X[i]}); bit.upd(f,-1); bit.upd(s,1); int sm=bit.sum(s); int move=sm-X[i]-1; if(f<s) range_upd(1,1,2*n,f+1,s-1,-1); else{ range_upd(1,1,2*n,s+1,f-1,1); } point_upd(1,1,2*n,f,0); point_upd(1,1,2*n,s,move); ans.pb(max(0,st[1])); 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...