#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }
using namespace std;
typedef long long ll;
typedef pair<int,int> Pair;
const int inf = 1e9;
const int Nmax = 4e5 + 5;
int L[Nmax], R[Nmax], ans[Nmax], H[Nmax], A[Nmax], B[Nmax];
int n, q;
vector<int> when[Nmax], add[Nmax], er[Nmax];
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
class SegTree
{
int val[Nmax<<2], best[Nmax<<2], lazy[Nmax<<2];
void propag(int node)
{
if(lazy[node] == inf) return;
lazy[left_son] = min(lazy[left_son], lazy[node]);
best[left_son] = max(best[left_son], val[left_son] - lazy[left_son]);
lazy[right_son] = min(lazy[right_son], lazy[node]);
best[right_son] = max(best[right_son], val[right_son] - lazy[right_son]);
lazy[node] = inf;
}
public:
void init(int node, int st, int dr)
{
best[node] = -inf;
val[node] = -inf;
lazy[node] = inf;
if(st == dr) return;
init(left_son, st, mid);
init(right_son, mid+1, dr);
}
void upd1(int node, int st, int dr, int pos, int mxVal)
{
if(st == dr)
{
val[node] = mxVal;
// best[node] = max(best[node], val[node] - lazy[node]);
lazy[node] = inf;
return;
}
propag(node);
if(pos <= mid) upd1(left_son, st, mid, pos, mxVal);
else upd1(right_son, mid+1, dr, pos, mxVal);
val[node] = max(val[left_son], val[right_son]);
best[node] = max(best[left_son], best[right_son]);
}
void upd2(int node, int st, int dr, int L, int R, int mnVal)
{
if(L <= st && dr <= R)
{
lazy[node] = min(lazy[node], mnVal);
best[node] = max(best[node], val[node] - lazy[node]);
return;
}
propag(node);
if(L <= mid) upd2(left_son, st, mid, L, R, mnVal);
if(mid < R) upd2(right_son, mid+1, dr, L, R, mnVal);
// val[node] = max(val[left_son], val[right_son]);
best[node] = max(best[left_son], best[right_son]);
}
int query(int node, int st, int dr, int L, int R)
{
if(L > dr || R < st) return -inf;
if(L <= st && dr <= R) return best[node];
propag(node);
return max( query(left_son, st, mid, L, R), query(right_son, mid+1, dr, L, R) );
}
} aint;
void solve()
{
aint.init(1, 1, n);
int i;
for(i=1; i<=n; ++i)
{
add[i+A[i]].push_back(i);
er[i+B[i]].push_back(i);
}
for(i=1; i<=q; ++i)
when[R[i]].push_back(i);
for(i=1; i<=n; ++i)
{
for(auto it : add[i])
aint.upd1(1, 1, n, it, H[it]);
int l, r;
l = max(1, i - B[i]);
r = max(1, i - A[i]);
aint.upd2(1, 1, n, l, r, H[i]);
for(auto it : when[i])
ans[it] = max(ans[it], aint.query(1, 1, n, L[it], i));
for(auto it : er[i])
aint.upd1(1, 1, n, it, -inf);
}
}
void clr()
{
int i;
for(i=1; i<=n; ++i)
{
when[i].clear();
add[i].clear();
er[i].clear();
}
}
int main()
{
cin.sync_with_stdio(false); cin.tie(0);
int i;
cin >> n;
for(i=1; i<=n; ++i) cin >> H[i] >> A[i] >> B[i];
cin >> q;
for(i=1; i<=q; ++i)
{
ans[i] = -1;
cin >> L[i] >> R[i];
}
solve();
clr();
for(i=1; i<=q; ++i)
{
L[i] = n+1-L[i];
R[i] = n+1-R[i];
swap(L[i], R[i]);
}
reverse(H+1, H+n+1);
reverse(A+1, A+n+1);
reverse(B+1, B+n+1);
solve();
for(i=1; i<=q; ++i) cout << ans[i] << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
28544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
28544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
450 ms |
53492 KB |
Output is correct |
2 |
Correct |
516 ms |
55592 KB |
Output is correct |
3 |
Correct |
356 ms |
49400 KB |
Output is correct |
4 |
Correct |
513 ms |
55496 KB |
Output is correct |
5 |
Correct |
235 ms |
41208 KB |
Output is correct |
6 |
Correct |
512 ms |
55544 KB |
Output is correct |
7 |
Correct |
479 ms |
52692 KB |
Output is correct |
8 |
Correct |
510 ms |
55456 KB |
Output is correct |
9 |
Correct |
84 ms |
32760 KB |
Output is correct |
10 |
Correct |
502 ms |
55548 KB |
Output is correct |
11 |
Correct |
294 ms |
44664 KB |
Output is correct |
12 |
Correct |
508 ms |
55556 KB |
Output is correct |
13 |
Correct |
270 ms |
50800 KB |
Output is correct |
14 |
Correct |
263 ms |
50240 KB |
Output is correct |
15 |
Correct |
266 ms |
50036 KB |
Output is correct |
16 |
Correct |
252 ms |
50804 KB |
Output is correct |
17 |
Correct |
270 ms |
51092 KB |
Output is correct |
18 |
Correct |
282 ms |
50172 KB |
Output is correct |
19 |
Correct |
270 ms |
50304 KB |
Output is correct |
20 |
Correct |
263 ms |
50500 KB |
Output is correct |
21 |
Correct |
266 ms |
51452 KB |
Output is correct |
22 |
Correct |
268 ms |
50548 KB |
Output is correct |
23 |
Correct |
281 ms |
50468 KB |
Output is correct |
24 |
Correct |
260 ms |
49912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
28544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |