Submission #208257

#	Time	Username	Problem	Language	Result	Execution time	Memory
208257		igzi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3012 ms	58108 KiB

sortbooks

#include <bits/stdc++.h>
#define maxN 1000006

using namespace std;

struct segment{
int M,m,res;
};
int a[maxN],n,m,i,l,d,k;
segment seg[4*maxN];

void build(int n,int l,int d){
if(l==d){
    seg[n].m=seg[n].M=a[l];
    seg[n].res=0;
    return;
}
int m=(l+d)/2;
build(2*n,l,m);
build(2*n+1,m+1,d);
seg[n].m=min(seg[2*n].m,seg[2*n+1].m);
seg[n].M=max(seg[2*n].M,seg[2*n+1].M);
seg[n].res=max(seg[2*n].res,seg[2*n+1].res);
seg[n].res=max(seg[n].res,seg[2*n].M-seg[2*n+1].m);
}

segment resi(int n,int l,int d,int x,int y){
if(d<x || l>y){
segment a;
a.M=a.res=0;
a.m=10000000002;
return a;
}
if(l>=x && d<=y){
return seg[n];
}
int m=(l+d)/2;
segment a,b,r;
a=resi(2*n,l,m,x,y);
b=resi(2*n+1,m+1,d,x,y);
r.m=min(a.m,b.m);
r.M=max(a.M,b.M);
r.res=max(a.res,b.res);
r.res=max(r.res,a.M-b.m);
//cout<<l<<" "<<d<<" "<<r.m<<endl;
return r;
}

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;
        segment a=resi(1,0,n-1,l-1,d-1);
        if(a.res<=k) cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'segment resi(int, int, int, int, int)':
sortbooks.cpp:31:5: warning: overflow in implicit constant conversion [-Woverflow]
 a.m=10000000002;
     ^~~~~~~~~~~

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