#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define SZ(x) (int)((x).size())
const ll maxn = 2005;
const ll inf = (1ll<<60);
const ll mod = 1e9+7;
vector<int> seg(4*maxn);
int query(int l, int r, int nl, int nr, int x){
if (l > nr || r < nl) return -1;
if (l <= nl && nr <= r) return seg[x];
int mid = (nl+nr)>>1;
return max(query(l, r, nl, mid, x+x), query(l, r, mid+1, nr, x+x+1));
}
void modify(int l, int r, int p, int v, int x){
if (l == r){
seg[x] = max(seg[x], v);
return;
}
int mid = (l+r)>>1;
if (l <= p && p <= mid){
modify(l, mid, p, v, x+x);
}
else modify(mid+1, r, p, v, x+x+1);
seg[x] = max(seg[x+x], seg[x+x+1]);
}
vector<int> ans(maxn);
int n, q;
vector<pip> in;
vector<pip> md, qu;
bool cmp(pip a, pip b){
return a.s.s < b.s.s;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
fill(ALL(seg), -1);
cin>>n;
in.pb({0, {0, 0}});
REP1(i, n){
int h, a, b; cin>>h>>a>>b;
in.pb({h, {a, b}});
for (int j = i-a; j >= 1; j--){
if (i-j > b) break;
if (in[j].s.f <= i-j && in[j].s.s >= i-j){
md.pb({abs(in[j].f-in[i].f), {j, i}});
}
}
}
cin>>q;
REP(i, q){
int l, r; cin>>l>>r;
qu.pb({i, {l, r}});
}
sort(ALL(md), cmp);
sort(ALL(qu), cmp);
int pa = 0;
REP(i, q){
while(pa < SZ(md) && md[pa].s.s <= qu[i].s.s){
modify(1, n, md[pa].s.f, md[pa].f, 1);
pa++;
}
ans[qu[i].f] = query(qu[i].s.f, qu[i].s.s, 1, n, 1);
}
REP(i, q) cout<<ans[i]<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
672 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
532 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
544 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
544 KB |
Output is correct |
| 20 |
Correct |
1 ms |
600 KB |
Output is correct |
| 21 |
Correct |
1 ms |
540 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
672 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
532 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
544 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
544 KB |
Output is correct |
| 20 |
Correct |
1 ms |
600 KB |
Output is correct |
| 21 |
Correct |
1 ms |
540 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Runtime error |
47 ms |
13144 KB |
Execution killed with signal 11 |
| 26 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
486 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
672 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
532 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
544 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
544 KB |
Output is correct |
| 20 |
Correct |
1 ms |
600 KB |
Output is correct |
| 21 |
Correct |
1 ms |
540 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Runtime error |
47 ms |
13144 KB |
Execution killed with signal 11 |
| 26 |
Halted |
0 ms |
0 KB |
- |
