Submission #469023

#TimeUsernameProblemLanguageResultExecution timeMemory
469023stefantagaBubble Sort 2 (JOI18_bubblesort2)C++14
60 / 100
1416 ms524292 KiB
#include "bubblesort2.h" #define INF 10000000000000 #include <cstdio> #include <cstdlib> #include <vector> #include <bits/stdc++.h> using namespace std; int nr,n,i,v[500005]; map <pair <int,int> ,int> m; long long arb[2000005],lazy[2000005]; void propaga(int st,int dr,int nod) { if (st==dr) { return; } if (lazy[nod]==0) { return; } lazy[2*nod]+=lazy[nod]; lazy[2*nod+1]+=lazy[nod]; arb[2*nod]+=lazy[nod]; arb[2*nod+1]+=lazy[nod]; lazy[nod]=0; return; } void update(int st,int dr,int nod,int ua,int ub,long long val) { if (ua<=st&&dr<=ub) { arb[nod]+=val; lazy[nod]+=val; return ; } propaga(st,dr,nod); int mij=(st+dr)/2; if (ua<=mij) { update(st,mij,2*nod,ua,ub,val); } if (mij<ub) { update(mij+1,dr,2*nod+1,ua,ub,val); } arb[nod]=max(arb[2*nod],arb[2*nod+1]); } std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> val){ int q=X.size(); n=A.size(); for (i=0;i<n;i++) { v[i+1]=A[i]; } for (i=1;i<=n;i++) { m[{v[i],i}]=1; } for (i=0;i<q;i++) { m[{val[i],X[i]+1}]=1; } nr=0; for (auto ind: m) { nr++; m[ind.first]=nr; } update(1,nr,1,1,nr,-INF); for (i=1;i<=n;i++) { v[i]=m[{v[i],i}]; update(1,nr,1,v[i],v[i],INF+i); update(1,nr,1,v[i]+1,nr,-1); } int j; vector <int> sol; for (i=0;i<q;i++) { int poz=X[i]+1; update(1,nr,1,v[poz],v[poz],-INF-poz); update(1,nr,1,v[poz]+1,nr,1); v[poz]=m[{val[i],poz}]; update(1,nr,1,v[poz],v[poz],INF+poz); update(1,nr,1,v[poz]+1,nr,-1); sol.push_back(arb[1]-1); } return sol; } /*int readInt(){ int i; if(scanf("%d",&i)!=1){ fprintf(stderr,"Error while reading input\n"); exit(1); } return i; } int main(){ int N,Q; N=readInt(); Q=readInt(); std::vector<int> A(N); for(int i=0;i<N;i++) A[i]=readInt(); std::vector<int> X(Q),V(Q); for(int j=0;j<Q;j++){ X[j]=readInt(); V[j]=readInt(); } std::vector<int> res=countScans(A,X,V); for(int j=0;j<int(res.size());j++) printf("%d\n",res[j]); }*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:77:9: warning: unused variable 'j' [-Wunused-variable]
   77 |     int j;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...