Submission #996841

#	Time	Username	Problem	Language	Result	Execution time	Memory
996841		pera	Two Antennas (JOI19_antennas)	C++17	0 / 100	226 ms	42836 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 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]);
   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 ANS[u];
   }
   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;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65