#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;
int n, q;
ll a[1000009];
pair<pair<pii, ll>, int> tv[1000009];
ll st[4000009];
ll mx[4000009];
pll lazy[4000009];
ll luoi[4000009];
bool kq[1000009];
vector<int> query[1000009][2];
void build(int goc = 1, int l = 1, int r = q)
{
lazy[goc] = {-1, 0};
luoi[goc] = -1;
if (l == r)
{
st[goc] = -1e9;
mx[goc] = -1e9;
return;
}
int mid = (l+r)/2;
build(goc*2,l,mid);
build(goc*2+1,mid+1,r);
st[goc] = max(st[goc*2], st[goc*2+1]);
}
void down(int goc, int l, int r)
{
st[goc] = max(st[goc], lazy[goc].st);
st[goc] += lazy[goc].nd;
mx[goc] = max(mx[goc], st[goc]);
if (l != r)
{
lazy[goc*2].st = max(lazy[goc*2].st, lazy[goc].st - lazy[goc*2].nd);
lazy[goc*2].nd += lazy[goc].nd;
lazy[goc*2+1].st = max(lazy[goc*2+1].st, lazy[goc].st - lazy[goc*2+1].nd);
lazy[goc*2+1].nd += lazy[goc].nd;
}
lazy[goc] = {-1, 0};
}
void update1(int d, int c, int gt, int goc = 1, int l = 1, int r = q)
{
down(goc,l,r);
if (c < l || d > r) return;
if (d <= l && r <= c)
{
lazy[goc].st = gt;
down(goc,l,r);
return;
}
int mid = (l+r)/2;
update1(d,c,gt,goc*2,l,mid);
update1(d,c,gt,goc*2+1,mid+1,r);
st[goc] = max(st[goc*2], st[goc*2+1]);
}
void update2(int d, int c, int gt, int goc = 1, int l = 1, int r = q)
{
down(goc,l,r);
if (c < l || d > r) return;
if (d <= l && r <= c)
{
lazy[goc].nd += gt;
down(goc,l,r);
return;
}
int mid = (l+r)/2;
update2(d,c,gt,goc*2,l,mid);
update2(d,c,gt,goc*2+1,mid+1,r);
st[goc] = max(st[goc*2], st[goc*2+1]);
}
void xuong(int goc, int l, int r)
{
mx[goc] = max(mx[goc], luoi[goc]);
if (l != r)
{
luoi[goc*2] = max(luoi[goc*2], luoi[goc]);
luoi[goc*2+1] = max(luoi[goc*2+1], luoi[goc]);
}
luoi[goc] = -1;
}
void capnhat(int d, int c, int goc = 1, int l = 1, int r = q)
{
xuong(goc,l,r);
if (c < l || d > r) return;
if (d <= l && r <= c)
{
luoi[goc] = max(luoi[goc], st[goc]);
xuong(goc,l,r);
return;
}
int mid = (l+r)/2;
capnhat(d,c,goc*2,l,mid);
capnhat(d,c,goc*2+1,mid+1,r);
mx[goc] = max(mx[goc*2], mx[goc*2+1]);
}
ll get(int d, int c, int goc = 1, int l = 1, int r = q)
{
down(goc,l,r);
if (c < l || d > r) return -1e9;
if (d <= l && r <= c) return st[goc];
int mid = (l+r)/2;
return max(get(d,c,goc*2,l,mid), get(d,c,goc*2+1,mid+1,r));
}
ll lay(int d, int c, int goc = 1, int l = 1, int r = q)
{
xuong(goc,l,r);
if (c < l || d > r) return -1e9;
if (d <= l && r <= c) return mx[goc];
int mid = (l+r)/2;
return max(lay(d,c,goc*2,l,mid), lay(d,c,goc*2+1,mid+1,r));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
if (fopen(HTManh".inp", "r"))
{
freopen(HTManh".inp", "r", stdin);
freopen(HTManh".out", "w", stdout);
}
cin >> n >> q;
fi(i,1,n) cin >> a[i];
fi(i,1,q) cin >> tv[i].st.st.st >> tv[i].st.st.nd >> tv[i].st.nd;
fi(i,1,q) tv[i].nd = i;
sort(tv+1,tv+q+1);
fi(i,1,q)
{
query[tv[i].st.st.st][0].pb(i);
query[tv[i].st.st.nd][1].pb(i);
}
build();
int ctro = 0;
fi(i,1,n)
{
for(int x: query[i][0])
{
update1(x,x,a[i]);
ctro = x;
}
update1(1,ctro,a[i]);
// fi(i,1,q) cout << get(i,i) << " ";
// cout << endl;
int d = 1, c = q;
while(d <= c)
{
int g = (d+c)/2;
if (get(g,n) <= a[i]) c = g - 1;
else d = g + 1;
}
update2(1,c,a[i]);
// fi(i,1,q) cout << get(i,i) << " ";
// cout << endl;
capnhat(1,c);
update2(1,c,-a[i]);
// fi(i,1,q) cout << lay(i,i) << " ";
// cout << endl;
// cout << endl;
for(int x: query[i][1])
{
ll gt = lay(x,x);
if (gt <= tv[x].st.nd) kq[tv[x].nd] = 1;
}
}
fi(i,1,q) cout << kq[i] << endl;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | freopen(HTManh".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | freopen(HTManh".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
59992 KB |
Output is correct |
| 2 |
Correct |
7 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
59996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
59992 KB |
Output is correct |
| 2 |
Correct |
7 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
59996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
204892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
570 ms |
76036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
59992 KB |
Output is correct |
| 2 |
Correct |
7 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
59996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
59992 KB |
Output is correct |
| 2 |
Correct |
7 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
59996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
