Submission #996873

#TimeUsernameProblemLanguageResultExecution timeMemory
996873peraTwo Antennas (JOI19_antennas)C++17
0 / 100
1 ms348 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...