Submission #209787

#	Time	Username	Problem	Language	Result	Execution time	Memory
209787		igzi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3104 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#define maxN 1000006
 
using namespace std;
 
struct segment{
vector <int> v;
int res;
};
int a[maxN],n,m,i,l,d,k,ans,M;
segment seg[4*maxN];
 
void build(int n,int l,int d){
if(l==d){
    seg[n].v.push_back(a[l]);
    seg[n].res=0;
    return;
}
int m=(l+d)/2,tmp;
build(2*n,l,m);
build(2*n+1,m+1,d);
if(n!=1){
int i,j;
i=j=0;
while(i<seg[2*n].v.size() & j<seg[2*n+1].v.size()){
    if(seg[2*n].v[i]<=seg[2*n+1].v[j]) {seg[n].v.push_back(seg[2*n].v[i]); i++;}
    else {seg[n].v.push_back(seg[2*n+1].v[j]); j++;}
}
tmp=j-1;
while(i<seg[2*n].v.size()) {seg[n].v.push_back(seg[2*n].v[i]); i++;}
while(j<seg[2*n+1].v.size()) {seg[n].v.push_back(seg[2*n+1].v[j]); j++;}}
else seg[n].v.push_back(max(seg[2*n].v.back(),seg[2*n+1].v.back()));
M=seg[2*n].v.back();
seg[n].res=max(seg[2*n].res,seg[2*n+1].res);
if(n==1){
tmp=lower_bound(seg[2*n+1].v.begin(),seg[2*n+1].v.end(),M)-seg[2*n+1].v.begin()-1;
}
if(tmp>=0) seg[n].res=max(seg[n].res,seg[2*n+1].v[tmp]+M);
}
 
void resi(int n,int l,int d,int x,int y){
if(d<x || l>y || ans==0){
return;
}
if(l>=x && d<=y){
//cout<<l<<" "<<d<<" "<<M<<" "<<seg[n].res<<endl;
int tmp=lower_bound(seg[n].v.begin(),seg[n].v.end(),M)-seg[n].v.begin();
tmp--;
if(tmp>=0 && seg[n].v[tmp]+M>k) ans=0;
if(seg[n].res>k) ans=0;
M=max(M,seg[n].v.back());
return;
}
int m=(l+d)/2;
resi(2*n,l,m,x,y);
resi(2*n+1,m+1,d,x,y);
}
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    build(1,0,n-1);
    for(i=0;i<m;i++){
        cin>>l>>d>>k;
        ans=1;
        M=0;
        resi(1,0,n-1,l-1,d-1);
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:25:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<seg[2*n].v.size() & j<seg[2*n+1].v.size()){
       ~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:25:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<seg[2*n].v.size() & j<seg[2*n+1].v.size()){
                             ~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:25:8: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
 while(i<seg[2*n].v.size() & j<seg[2*n+1].v.size()){
       ~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:30:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<seg[2*n].v.size()) {seg[n].v.push_back(seg[2*n].v[i]); i++;}
       ~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:31:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(j<seg[2*n+1].v.size()) {seg[n].v.push_back(seg[2*n+1].v[j]); j++;}}
       ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23