Submission #993081

#TimeUsernameProblemLanguageResultExecution timeMemory
993081vivkostovHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
3072 ms241384 KiB
#include<bits/stdc++.h> #define endl "\n" using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int n,q,a[1000005],l,r,c,cost[4000005]; vector<int>p[4000005]; int merg(vector<int>v1,vector<int>v2,vector<int>&v) { int p1=0,p2=0,cos=0; for(int i=1;i<=v1.size()+v2.size();i++) { if(p1==v1.size()) { v.push_back(v2[p2]); p2++; } else if(p2==v2.size()) { v.push_back(v1[p1]); cos=max(v2[p2-1]+v1[p1],cos); p1++; } else if(v1[p1]>v2[p2]) { v.push_back(v2[p2]); p2++; cos=max(cos,v2[p2-1]+v1[p1]); } else { v.push_back(v1[p1]); p1++; } } return cos; } void check(int l,int r,int h) { cout<<l<<" "<<r<<" "<<cost[h]<<" | "; for(int i=0;i<p[h].size();i++) { cout<<p[h][i]<<" "; } cout<<endl; if(l==r)return; int m=(l+r)/2; check(l,m,h*2); check(m+1,r,h*2+1); } void build_tree(int l,int r,int h) { if(l==r) { p[h].push_back(a[l]); return; } int m=(l+r)/2; build_tree(l,m,h*2); build_tree(m+1,r,h*2+1); cost[h]=merg(p[h*2],p[h*2+1],p[h]); cost[h]=max(max(cost[h*2],cost[h*2+1]),cost[h]); } int otg[10005],ot,maotg; void query(int l,int r,int ql,int qr,int h) { if(r<ql||l>qr)return; if(l>=ql&&r<=qr) { //cout<<l<<" "<<r<<endl; ot++; otg[ot]=h; maotg=max(maotg,cost[h]); return; } int m=(l+r)/2; query(l,m,ql,qr,h*2); query(m+1,r,ql,qr,h*2+1); } void make_otg() { for(int i=1;i<ot;i++) { int w=p[otg[i]][p[otg[i]].size()-1]; for(int j=i+1;j<=ot;j++) { int l=0,r=p[otg[j]].size()-1,m; while(l<=r) { m=(l+r)/2; if(w<=p[otg[j]][m])l=m+1; else r=m-1; } if(l==0)continue; if(l==p[otg[j]].size())l--; maotg=max(maotg,w+p[otg[j]][l-1]); } //cout<<endl; otg[i]=0; } otg[ot]=0; ot=0; } void read() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; } build_tree(1,n,1); //check(1,n,1); for(int i=1;i<=q;i++) { cin>>l>>r>>c; query(1,n,l,r,1); make_otg(); //cout<<maotg<<" "; if(maotg<=c)cout<<1<<endl; else cout<<0<<endl; maotg=0; } } int main() { speed(); read(); return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int merg(std::vector<int>, std::vector<int>, std::vector<int>&)':
sortbooks.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=1;i<=v1.size()+v2.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:17:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         if(p1==v1.size())
      |            ~~^~~~~~~~~~~
sortbooks.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         else if(p2==v2.size())
      |                 ~~^~~~~~~~~~~
sortbooks.cpp: In function 'void check(int, int, int)':
sortbooks.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<p[h].size();i++)
      |                 ~^~~~~~~~~~~~
sortbooks.cpp: In function 'void make_otg()':
sortbooks.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             if(l==p[otg[j]].size())l--;
      |                ~^~~~~~~~~~~~~~~~~~
#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...