Submission #997236

#	Time	Username	Problem	Language	Result	Execution time	Memory
997236		pera	Two Antennas (JOI19_antennas)	C++17	100 / 100	478 ms	67908 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n , q;
vector<int> L(N) , R(N) , A(N) , B(N) , H(N) , ans(N);
vector<vector<int>> queries(N) , turn_on(N) , turn_off(N);
struct node{
   int mn_in = 1e9 + 1 , mx_in = -1 , mn_out = 1e9 + 1 , mx_out = -1 , ans = -1;
};
vector<node> t(4 * N);
void upd_ans(int u){
   t[u].ans = max({t[u].ans , t[u].mx_out - t[u].mn_in , t[u].mx_in - t[u].mn_out});
}
void push(int u){
   if(t[u].mx_out < 0){
      return;
   }
   t[u * 2].mn_out = min(t[u * 2].mn_out , t[u].mn_out);
   t[u * 2 + 1].mn_out = min(t[u * 2 + 1].mn_out , t[u].mn_out);
   t[u * 2].mx_out = max(t[u * 2].mx_out , t[u].mx_out);
   t[u * 2 + 1].mx_out = max(t[u * 2 + 1].mx_out , t[u].mx_out);
   upd_ans(u * 2);
   upd_ans(u * 2 + 1);
   t[u].mn_out = 1e9 + 1;
   t[u].mx_out = -1;
}
void update(int u , int l , int r , int pos , int x){
   push(u);
   if(l == r){
      if(x != -1){
        t[u].mn_in = t[u].mx_in = x;   
      }else{
        t[u].mn_in = 1e9 + 1 , t[u].mx_in = -1;
      }
      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].mn_in = min(t[u * 2].mn_in , t[u * 2 + 1].mn_in);
   t[u].mx_in = max(t[u * 2].mx_in , t[u * 2 + 1].mx_in);
}
void UPD(int u , int l , int r , int L ,int R , int x){
   if(l > r || r < L || l > R){
      return;
   }
   push(u);
   if(L <= l && r <= R){
      t[u].mn_out = t[u].mx_out = x;
      upd_ans(u);
      return;
   }
   int m = (l + r) / 2;
   UPD(u * 2 , l , m , L , R , x);
   UPD(u * 2 + 1 , m + 1 , r , L , R , x);
   t[u].ans = max(t[u * 2].ans , t[u * 2 + 1].ans);
}
int GET(int u , int l ,int r , int L , int R){
   if(l > r || r < L || l > R){
      return -1;
   }
   if(L <= l && r <= R){
      return t[u].ans;
   }
   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] , -1);
      }
      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]) << '\n';
   }
}

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