#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <array>
#include <random>
#include <climits>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
template<typename A, typename B> ostream& operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) { os << sep << x, sep = ", "; } return os << '}'; }
void D_out() { cerr << endl; }
template<typename Head, typename... Tail> void D_out(Head H, Tail... T) { cerr << ' ' << H; D_out(T...); }
#ifdef DEBUG
#define D(...) cerr << '(' << #__VA_ARGS__ << "):", D_out(__VA_ARGS__)
#else
#define D(...)
#endif
#define int long long
#define ll long long
#define ld long double
#define f first
#define s second
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
struct Node {
int l, r, c, d, lazy;
Node *lft, *rht;
Node (int tl, int tr): l(tl), r(tr), c(0), d(-1), lazy(1e18) {
if (l + 1 != r) {
lft = new Node(l, (l + r) / 2);
rht = new Node((l + r) / 2, r);
} else {
lft = rht = NULL;
}
}
};
void propagate(Node *x) {
if (x->lazy != 1e18) {
x->lft->lazy = min(x->lft->lazy, x->lazy);
x->rht->lazy = min(x->rht->lazy, x->lazy);
x->lazy = 1e18;
}
}
void update1(Node *x, int pos, int v) {
if (pos < x->l || x->r <= pos) {
return;
}
if (x->l + 1 == x->r) {
x->c = v;
return;
}
propagate(x);
update1(x->lft, pos, v);
update1(x->rht, pos, v);
x->c = max(x->lft->c, x->rht->c);
x->d = max(x->lft->d, x->rht->d);
}
void update2(Node *x, int l, int r, int v) {
if (r <= x->l || x->r <= l) {
return;
}
if (l <= x->l && x->r <= r) {
x->lazy = v;
x->d = max(x->d, x->c - x->lazy);
return;
}
propagate(x);
update2(x->lft, l, r, v);
update2(x->rht, l, r, v);
x->c = max(x->lft->c, x->rht->c);
x->d = max(x->lft->d, x->rht->d);
}
int query(Node *x, int l, int r) {
if (r <= x->l || x->r <= l) {
return -1e18;
}
if (l <= x->l && x->r <= r) {
return x->d;
}
propagate(x);
return max(query(x->lft, l, r), query(x->rht, l, r));
}
int n, q, ans[200005];
vector<array<int, 3>> v;
vector<pair<int, int>> queries, currq[200005];
vector<int> make[200005], kill[200005];
Node *root;
void solve() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i][0] >> v[i][1] >> v[i][2];
}
cin >> q;
for (int i = 0, l, r; i < q; i++) {
cin >> l >> r;
l--;
r--;
queries.push_back({l, r});
}
fill(ans, ans + 200005, -1);
function<void()> sweep = [&] () {
root = new Node(0, 200005);
for (int i = 0; i < 200005; i++) {
currq[i].clear();
make[i].clear();
kill[i].clear();
}
for (int i = 0; i < q; i++) {
currq[queries[i].s].push_back({queries[i].f, i});
}
for (int i = 0; i < n; i++) {
if (i + v[i][1] < n) {
make[i + v[i][1]].push_back(i);
}
if (i + v[i][2] < n) {
kill[i + v[i][2]].push_back(i);
}
for (int j : make[i]) {
update1(root, j, v[j][0]);
}
if (i - v[i][1] >= 0) {
update2(root, max(i - v[i][2], 0ll), i - v[i][1] + 1, v[i][0]);
}
for (pair<int, int> j : currq[i]) {
ans[j.s] = max(ans[j.s], query(root, j.f, i + 1));
}
for (int j : kill[i]) {
update1(root, j, 0);
}
}
};
sweep();
reverse(all(v));
D(queries);
for (pair<int, int> &q : queries) {
int nqf = n - q.s - 1, nqs = n - q.f - 1;
q = {nqf, nqs};
}
D(queries);
sweep();
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1; //cin >> t;
for (int tc = 1; tc <= t; tc++) {
//cout << "Case #" << tc << ": ";
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
66128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
66128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
392 ms |
79444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
66128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
