Submission #58279

#TimeUsernameProblemLanguageResultExecution timeMemory
58279KmcodeBubble Sort 2 (JOI18_bubblesort2)C++14
0 / 100
44 ms3064 KiB
//#include "bubblesort2.h" #include <bits/stdc++.h> using namespace std; vector<pair<int,int> > lis; long long int seg[1<<20]; long long int lazy[1<<20]; void upd(int b){ seg[b]+=lazy[b]; if(b*2+2<(1<<20)){ lazy[b*2+1]+=lazy[b]; lazy[b*2+2]+=lazy[b]; } lazy[b]=0; } inline void add(int b,int l,int r,int ll,int rr,long long int x){ upd(b); if(r<=ll||rr<=l){ return; } if(ll<=l&&r<=rr){ lazy[b]+=x; upd(b); return; } add(b*2+1,l,(l+r)>>1,ll,rr,x); add(b*2+2,(l+r)>>1,r,ll,rr,x); seg[b]=max(seg[b*2+1],seg[b*2+2]); } int get_id(int pos,int val){ return lower_bound(lis.begin(),lis.end(),make_pair(val,pos))-lis.begin(); } vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){ for(int i=0;i<A.size();i++){ lis.push_back(make_pair(A[i],i)); } for(int i=0;i<X.size();i++){ X[i]--; lis.push_back(make_pair(V[i],X[i])); } sort(lis.begin(),lis.end()); lis.erase(unique(lis.begin(),lis.end()),lis.end()); for(int i=0;i<A.size();i++){ int z=get_id(i,A[i]); add(0,0,lis.size(),z,z+1,i); add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1); } vector<int> res; for(int ii=0;ii<X.size();ii++){ int i=X[ii]; int z=get_id(i,A[i]); add(0,0,lis.size(),z,z+1,-i); add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),1); A[i]=V[ii]; z=get_id(i,A[i]); add(0,0,lis.size(),z,z+1,i); add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1); upd(0); res.push_back(seg[0]); } return res; }

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int ii=0;ii<X.size();ii++){
               ~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...