Submission #445799

#TimeUsernameProblemLanguageResultExecution timeMemory
445799julian33Bubble Sort 2 (JOI18_bubblesort2)C++14
Compilation error
0 ms0 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; } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,q; cin>>n>>q; vector<int> a(n),x(q),v(q); for(int &i:a) cin>>i; for(int i=0;i<q;i++) cin>>x[i]>>v[i]; vector<int> res=countScans(a,x,v); for(int &i:res) cout<<i<<" "; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc0YtblY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqYX75Y.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status