Submission #709791

#TimeUsernameProblemLanguageResultExecution timeMemory
709791groshiHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
64 / 100
3037 ms188560 KiB
#include<iostream> #include<vector> using namespace std; const int T = 1<<20; vector<vector<int> > drzewo; int wynik[2*T]; int maxx=0; int wynikk=0; int pot=1; void dodaj(int x) { wynikk=max(wynikk,wynik[x]); if(drzewo[x].size()==0) return; int mam=drzewo[x].back(); int gdzie=lower_bound(drzewo[x].begin(),drzewo[x].end(),maxx)-drzewo[x].begin(); if(gdzie>=1) wynikk=max(wynikk,maxx+drzewo[x][gdzie-1]); maxx=max(maxx,mam); } void zapp(int x,int l,int r,int a,int b) { if(l>b || r<a) return; if(a<=l && r<=b) { dodaj(x); return; } int mid=(l+r)/2; zapp(x*2,l,mid,a,b); zapp(x*2+1,mid+1,r,a,b); } int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int n,zap,x; cin>>n>>zap; while(pot<=n) pot*=2; pot--; drzewo.resize(2*pot+2); for(int i=1;i<=n;i++) { cin>>x; drzewo[i+pot].push_back(x); } for(int i=pot;i>=1;i--) { ///merguje i*2 z i*2+1 wynik[i]=max(wynik[i*2],wynik[i*2+1]); if(drzewo[i*2].size()>0) { int jest=drzewo[i*2].back(); int gdzie=lower_bound(drzewo[i*2+1].begin(),drzewo[i*2+1].end(),jest)-drzewo[i*2+1].begin(); if(gdzie>=1) wynik[i]=max(wynik[i],jest+drzewo[i*2+1][gdzie-1]); } int l=0,r=0; while(l<drzewo[i*2].size() && r<drzewo[i*2+1].size()) { if(drzewo[i*2][l]<=drzewo[i*2+1][r]) { drzewo[i].push_back(drzewo[i*2][l]); l++; } else{ drzewo[i].push_back(drzewo[i*2+1][r]); r++; } } while(r<drzewo[i*2+1].size()) { drzewo[i].push_back(drzewo[i*2+1][r]); r++; } while(l<drzewo[i*2].size()) { drzewo[i].push_back(drzewo[i*2][l]); l++; } } while(zap--) { int x,y,z; cin>>x>>y>>z; maxx=0; wynikk=0; zapp(1,pot+1,pot*2+1,x+pot,y+pot); if(wynikk>z) cout<<"0\n"; else cout<<"1\n"; } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(l<drzewo[i*2].size() && r<drzewo[i*2+1].size())
      |               ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(l<drzewo[i*2].size() && r<drzewo[i*2+1].size())
      |                                       ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(r<drzewo[i*2+1].size())
      |               ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(l<drzewo[i*2].size())
      |               ~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...