#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 1000006
typedef long long ll;
using namespace std;
int n,m;
struct cvor{
int minimum,maksimum,najraz;
};
int niz[MAXN];
cvor seg[4*MAXN];
vector<cvor> tren;
vector<int> mi,ma;
int tres;
void izgradi(int l,int d,int k){
if(l==d){
seg[k].minimum=niz[l];
seg[k].maksimum=niz[l];
seg[k].najraz=0;
return;
}
int mid=(l+d)/2;
izgradi(l,mid,k+k);
izgradi(mid+1,d,k+k+1);
seg[k].najraz=max(max(seg[k+k].najraz,seg[k+k+1].najraz),seg[k+k].maksimum-seg[k+k+1].minimum);
seg[k].maksimum=max(seg[k+k].maksimum,seg[k+k+1].maksimum);
seg[k].minimum=min(seg[k+k].minimum,seg[k+k+1].minimum);
}
void resi(int l,int d,int tl,int td,int k){
if(l>td || d<tl)return;
if(l>=tl && d<=td){
tres=max(tres,seg[k].najraz);
mi.pb(seg[k].minimum);
ma.pb(seg[k].maksimum);
return;
}
int mid=(l+d)/2;
resi(l,mid,tl,td,k+k);
resi(mid+1,d,tl,td,k+k+1);
}
int main()
{
scanf("%d %d", &n, &m);
for(int i=1;i<=n;i++){
scanf("%d",niz+i);
}
izgradi(1,n,1);
while(m--){
tres=0;
mi.clear();
ma.clear();
int tl,td,k;
scanf("%d %d %d", &tl,&td, &k);
resi(1,n,tl,td,1);
for(int i=1;i<ma.size();i++){
ma[i]=max(ma[i-1],ma[i]);
}
for(int i=mi.size()-2;i>=0;i--){
mi[i]=min(mi[i+1],mi[i]);
}
for(int i=1;i<ma.size();i++){
tres=max(tres,ma[i-1]-mi[i]);
}
if(tres<=k)printf("1\n");
else printf("0\n");
}
return 0;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<ma.size();i++){
~^~~~~~~~~~
sortbooks.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<ma.size();i++){
~^~~~~~~~~~
sortbooks.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",niz+i);
~~~~~^~~~~~~~~~~~
sortbooks.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &tl,&td, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1577 ms |
52680 KB |
Output is correct |
2 |
Incorrect |
1574 ms |
63788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
109 ms |
5240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |