#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL
#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())
const int INF = 1e9 + 5;
struct Op
{
int mn, mx;
Op()
{
mn = INF;
mx = -INF;
}
Op(int a, int b)
{
mn = a;
mx = b;
}
Op& operator += (Op a)
{
mn = min(mn, a.mn);
mx = max(mx, a.mx);
return *this;
}
};
struct Node
{
int mn, mx, best;
Node()
{
mn = INF;
mx = -INF;
best = -INF;
}
Node(int _mn, int _mx, int _best = -INF)
{
mn = _mn;
mx = _mx;
best = _best;
}
void apply(Op op)
{
if(mn == INF) return;
best = max(best, max(mx - op.mn, op.mx - mn));
}
};
ostream& operator << (ostream& os, Node n) {return os << "(" << n.mn << ", " << n.mx << " -> " << n.best << ")";}
ostream& operator << (ostream& os, Op n) {return os << "(" << n.mn << ", " << n.mx << ")";}
bool operator != (Op a, Op b){ return a.mn != b.mn || a.mx != b.mx; }
bool operator == (Node a, Node b) {return a.mn == b.mn && a.mx == b.mx && a.best == b.best;}
Node operator + (Node a, Node b)
{
Node ret;
if(a == Node()) ret = b;
else if(b == Node()) ret = a;
else
{
ret.mn = min(a.mn, b.mn);
ret.mx = max(a.mx, b.mx);
ret.best = max(a.best, b.best);
}
return ret;
}
struct SegTree
{
vt<Node> S;
vt<Op> lazy;
int N;
SegTree(int _N)
{
N = 1;
while(N < _N) N *= 2;
S.resize(2 * N);
lazy.resize(2 * N);
}
void push(int i)
{
if(lazy[i] != Op())
{
S[i].apply(lazy[i]);
if(i < N)
{
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = Op();
}
}
int qry(int l, int r, int a, int b, int i)
{
push(i);
if(l <= a && b <= r) return S[i].best;
if(r < a || b < l) return -INF;
int m = (a + b) / 2;
return max(qry(l, r, a, m, 2 * i), qry(l, r, m + 1, b, 2 * i + 1));
}
int qry(int l, int r) {return qry(l, r, 1, N, 1);}
void apply(int l, int r, Op o, int a, int b, int i)
{
push(i);
if(l <= a && b <= r)
{
lazy[i] += o;
push(i);
return;
}
if(r < a || b < l) return;
int m = (a + b) / 2;
apply(l, r, o, a, m, 2 * i);
apply(l, r, o, m + 1, b, 2 * i + 1);
S[i] = S[2 * i] + S[2 * i + 1];
}
void apply(int l, int r, Op o) {apply(l, r, o, 1, N, 1);}
void upd(int i, Node n)
{
qry(i, i); //Clear lazy
int u = i + N - 1;
S[u] = n;
//dbg(u, S[u]);
for(u /= 2; u > 0; u /= 2)
{
S[u] = S[2 * u] + S[2 * u + 1];
}
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vt<int> H(N), A(N), B(N);
vt<vt<int>> act(N + 1), deact(N + 1), qry(N + 1);
for(int i = 0; i < N; i++)
{
cin >> H[i] >> A[i] >> B[i];
act[min(N, i + A[i])].pb(i);
deact[min(N, i + B[i] + 1)].pb(i);
}
int Q;
cin >> Q;
vt<int> ans(Q);
vt<int> lb(Q);
for(int i = 0; i < Q; i++)
{
int L, R;
cin >> L >> R, --L, --R;
qry[R].pb(i);
lb[i] = L;
}
SegTree s(N);
for(int i = 0; i < N; i++)
{
for(int x : deact[i]) s.upd(x + 1, Node());
//if(i == 2) dbg(s.S);
for(int x : act[i]) s.upd(x + 1, Node(H[x], H[x]));
//Apply myself
s.apply(1 + max(0, i - B[i]), 1 + max(-1, i - A[i]), Op(H[i], H[i]));
//if(i == 2) dbg(s.S);
for(int x : qry[i]) ans[x] = s.qry(1 + lb[x], i + 1);
}
for(int x : ans) cout << max(x, -1) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
300 ms |
33760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
