| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 996874 | pera | Two Antennas (JOI19_antennas) | C++17 | 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.
#include<bits/stdc++.h>
using namespace std;
const int N = 10 + 10;
int n , q;
vector<int> L(N) , R(N) , A(N) , B(N) , H(N) , ANS(N) , ans(N) , value(4 * N , -1) ;
vector<vector<int>> queries(N) , turn_on(N) , turn_off(N);
struct node{
int mn = 1e9 + 1 , mx = 0;
};
vector<node> t(4 * N) , lz(4 * N);
node MERGE(node x , node y){
node z;
z.mn = min(x.mn , y.mn);
z.mx = max(x.mx , y.mx);
return z;
}
void upd_ans(int u){
ANS[u] = max({ANS[u] , lz[u].mx - t[u].mn , t[u].mx - lz[u].mn});
}
void combine(int u){
lz[u] = MERGE(lz[u * 2] , lz[u * 2 + 1]);
t[u] = MERGE(t[u * 2] , t[u * 2 + 1]);
ANS[u] = max({ANS[u] , ANS[u * 2] , ANS[u * 2 + 1]});
}
void push(int u){
if(value[u] == -1){
return;
}
value[u * 2] = value[u * 2 + 1] = value[u];
lz[u * 2] = {value[u] ,value[u]};
lz[u * 2 + 1] = {value[u] , value[u]};
upd_ans(u * 2);
upd_ans(u * 2 + 1);
value[u] = -1;
}
void build(int u , int l , int r){
if(l == r){
t[u] = {(int)1e9 + 1 , 0};
lz[u] = {(int)1e9 + 1 , 0};
ANS[u] = 0;
return;
}
int m = (l + r) / 2;
build(u * 2 , l , m);
build(u * 2 + 1 , m + 1 , r);
combine(u);
}
void update(int u , int l , int r , int pos , int x){
if(l == r){
if(x == -1){
t[u] = {(int)1e9 + 1 , 0};
}else{
t[u] = {x , x};
}
return;
}
int m = (l + r) / 2;
if(pos <= m){
update(u * 2 , l , m , pos , x);
}else{
update(u * 2 + 1 , m + 1 , r , pos , x);
}
t[u] = MERGE(t[u * 2] , t[u * 2 + 1]);
}
void UPD(int u , int l , int r, int L , int R , int x){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
value[u] = x;
lz[u] = {x , x};
upd_ans(u);
return;
}
push(u);
int m = (l + r) / 2;
UPD(u * 2 , l , m , L , R , x);
UPD(u * 2 + 1 , m + 1 , r , L , R , x);
combine(u);
}
int GET(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return 0;
}
if(L <= l && r <= R){
return max(ANS[u] , t[u].mx - lz[u].mn , lz[u].mx - t[u].mn);
}
push(u);
int m = (l + r) / 2;
return max(GET(u * 2 , l , m , L , R) , GET(u * 2 + 1 , m + 1 , r , L , R));
}
int main(){
cin >> n;
for(int i = 1;i <= n;i ++){
cin >> H[i] >> A[i] >> B[i];
if(i + A[i] <= n){
turn_on[i + A[i]].push_back(i);
if(i + B[i] + 1 <= n){
turn_off[i + B[i] + 1].push_back(i);
}
}
}
cin >> q;
for(int i = 1;i <= q;i ++){
cin >> L[i] >> R[i];
queries[R[i]].push_back(i);
}
for(int i = 1;i <= n;i ++){
for(int x = 0;x < (int)turn_on[i].size();x ++){
update(1 , 1 , n , turn_on[i][x] , H[turn_on[i][x]]);
}
for(int x = 0;x < (int)turn_off[i].size();x ++){
update(1 , 1 , n , turn_off[i][x] , -1LL);
}
if(i - A[i] >= 1){
UPD(1 , 1 , n , max(1 , i - B[i]) , i - A[i] , H[i]);
}
for(int id : queries[i]){
ans[id] = GET(1 , 1 , n , L[id] , R[id]);
}
}
for(int i = 1;i <= q;i ++){
cout << (ans[i] == 0 ? -1 : ans[i]) << " ";
}
cout << endl;
}