Submission #993272

#TimeUsernameProblemLanguageResultExecution timeMemory
993272vivkostovHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
3058 ms252836 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]; mt19937 mt(time(nullptr)); 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]); cos=max(cos,v2[p2]+v1[p1]); p2++; } 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(l>qr||r<ql)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 dumb_query(int l,int r,int ql,int qr,int h) { if(l>qr||r<ql)return; if(l==r) { ot++; otg[ot]=h; return; } int m=(l+r)/2; dumb_query(l,m,ql,qr,h*2); dumb_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)maotg=max(maotg,w+p[otg[j]][l-1]); } //cout<<endl; otg[i]=0; } ot=0; } void dumb_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++) { for(int z=p[otg[j]].size()-1;z>=0;z--) { if(w>p[otg[j]][z]) { maotg=max(maotg,p[otg[j]][z]+w); break; } } } otg[i]=0; } ot=0; } void read() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; //a[i]=mt()%20+1; //cout<<a[i]<<" "; } //cout<<endl; 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); dumb_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:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=1;i<=v1.size()+v2.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(p1==v1.size())
      |            ~~^~~~~~~~~~~
sortbooks.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         else if(p2==v2.size())
      |                 ~~^~~~~~~~~~~
sortbooks.cpp: In function 'void check(int, int, int)':
sortbooks.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<p[h].size();i++)
      |                 ~^~~~~~~~~~~~
#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...