Submission #469003

#TimeUsernameProblemLanguageResultExecution timeMemory
469003stefantagaBubble Sort 2 (JOI18_bubblesort2)C++14
38 / 100
9017 ms1860 KiB
#include "bubblesort2.h" #include <cstdio> #include <cstdlib> #include <vector> #include <bits/stdc++.h> using namespace std; int aib[500005]; int ub(int x) { return x&(-x); } int nr,n,i,v[500005]; map <int,int> m; void update(int poz,int val) { int i; for (i=poz;i<=nr;i+=ub(i)) { aib[i]+=val; } } int suma(int poz) { int i,sum=0; for (i=poz;i>=1;i-=ub(i)) { sum=sum+aib[i]; } return sum; } 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]]=1; } for (i=0;i<q;i++) { m[val[i]]=1; } nr=0; for (auto ind: m) { nr++; m[ind.first]=nr; } for (i=1;i<=n;i++) { v[i]=m[v[i]]; } int j; vector <int> sol; for (i=0;i<q;i++) { v[X[i]+1]=m[val[i]]; int maxim=0; for (j=1;j<=n;j++) { maxim=max(maxim,suma(nr)-suma(v[j])); update(v[j],1); } for (j=1;j<=n;j++) { update(v[j],-1); } sol.push_back(maxim); } 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]); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...