| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 105843 | Pro_ktmr | Two Antennas (JOI19_antennas) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
struct RMinQ{
private:
int N;
vector<LL> node,lazy;
public:
void init(int n){
N = 1;
while(N < n) N *= 2;
for(int i=0; i<2*N-1; i++) node.PB(INT_MAX);
for(int i=0; i<2*N-1; i++) lazy.PB(INT_MAX);
}
void eval(int k, int l, int r){
if(lazy[k] == INT_MAX) return;
node[k] = min(node[k], lazy[k]);
if(r-l != 0){
lazy[2*k+1] = min(lazy[2*k+1],lazy[k]);
lazy[2*k+2] = min(lazy[2*k+2],lazy[k]);
}
lazy[k] = INT_MAX;
}
void update(int a, int b, int x, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
lazy[k] = x;
eval(k, l, r);
}
update(a, b, 2*k+1, l, (l+r)/2);
update(a, b, 2*k+2, (l+r)/2, r);
node[k] = min(node[2*k+1], node[2*k+2]);
}
LL query(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return INT_MAX;
if(a <= l && r <= b) return node[k];
return min(query(a, b, 2*k+1, l, (l+r)/2),query(a, b, 2*k+2, (l+r)/2, r));
}
};
struct RMaxQ{
private:
int N;
vector<LL> node,lazy;
public:
void init(int n){
N = 1;
while(N < n) N *= 2;
for(int i=0; i<2*N-1; i++) node.PB(INT_MIN);
for(int i=0; i<2*N-1; i++) lazy.PB(INT_MIN);
}
void eval(int k, int l, int r){
if(lazy[k] == INT_MIN) return;
node[k] = max(node[k], lazy[k]);
if(r-l != 0){
lazy[2*k+1] = max(lazy[2*k+1],lazy[k]);
lazy[2*k+2] = max(lazy[2*k+2],lazy[k]);
}
lazy[k] = INT_MIN;
}
void update(int a, int b, int x, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
lazy[k] = x;
eval(k, l, r);
}
update(a, b, 2*k+1, l, (l+r)/2);
update(a, b, 2*k+2, (l+r)/2, r);
node[k] = max(node[2*k+1], node[2*k+2]);
}
LL query(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return INT_MIN;
if(a <= l && r <= b) return node[k];
return min(query(a, b, 2*k+1, l, (l+r)/2),query(a, b, 2*k+2, (l+r)/2, r));
}
};
int N,H[200000],A[200000],B[200000],Q,L[200000],R[200000];
vector<pair<pair<int,int>,int>> v,q;
int ans[200000];
int main(){
scanf("%d", &N);
if(N > 2000) return -1;
for(int i=0; i<N; i++){
scanf("%d%d%d", H+i, A+i, B+i);
}
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
int d = j-i;
if(d < A[i] || d < A[j] || B[i] < d || B[j] < d) continue;
v.PB(MP(MP(i+1,j+1),abs(H[i]-H[j])));
}
}
sort(v.begin(), v.end());
scanf("%d", &Q);
for(int i=0; i<Q; i++){
scanf("%d%d", L+i, R+i);
q.PB(MP(MP(L[i],R[i]),i));
}
sort(q.begin(), q.end());
RMQ rsq;
rsq.init(N+1);
int now = v.size()-1;
for(int i=Q-1; i>=0; i--){
while(now >= 0 && v[now].first.first >= q[i].first.first){
rsq.update(v[now].first.second, v[now].second);
now--;
}
ans[q[i].second] = rsq.sum(q[i].first.first, q[i].first.second+1);
}
for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
return 0;
}