Submission #709778

#TimeUsernameProblemLanguageResultExecution timeMemory
709778groshiHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
64 / 100
472 ms165552 KiB
#include<iostream> #include<vector> using namespace std; vector<int> drzewo[2000000]; int wynik[2000000]; 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(); if(maxx==0) { maxx=mam; return; } int gdzie=lower_bound(drzewo[x].begin(),drzewo[x].end(),maxx)-drzewo[x].begin(); if(gdzie>=1 && gdzie<=drzewo[x].size()) 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--; 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 && gdzie<=drzewo[i*2+1].size()) 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(l==drzewo[i*2].size()) { drzewo[i].push_back(drzewo[i*2+1][r]); r++; continue; } if(r==drzewo[i*2+1].size()) { drzewo[i].push_back(drzewo[i*2][l]); l++; continue; } 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(zap--) { int x,y,z; cin>>x>>y>>z; maxx=0; wynikk=0; zapp(1,pot+1,pot*2+1,x+pot,y+pot); //cout<<wynikk<<"\n"; if(wynikk>z) cout<<"0\n"; else cout<<"1\n"; } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'void dodaj(int)':
sortbooks.cpp:21:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(gdzie>=1 && gdzie<=drzewo[x].size())
      |                    ~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:61:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if(gdzie>=1 && gdzie<=drzewo[i*2+1].size())
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while(l<drzewo[i*2].size() || r<drzewo[i*2+1].size())
      |               ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:65:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while(l<drzewo[i*2].size() || r<drzewo[i*2+1].size())
      |                                       ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if(l==drzewo[i*2].size())
      |                ~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if(r==drzewo[i*2+1].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...