Submission #996721

#	Time	Username	Problem	Language	Result	Execution time	Memory
996721		pera	Two Antennas (JOI19_antennas)	C++17	22 / 100	450 ms	68328 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n , q;
vector<int> A(N) , B(N);
vector<long long> H(N);
vector<vector<int>> turn_on(N) , turn_off(N) ;
vector<vector<long long>> t(4 * N , vector<long long>(2));
void build(int u , int l , int r){
   if(l == r){
      t[u][0] = 0LL;
      t[u][1] = (long long)1e9 + 1;
      return;
   }
   int m = (l + r) / 2;
   build(u * 2 , l , m);
   build(u * 2 + 1 , m + 1 , r);
   t[u][0] = max(t[u * 2][0] , t[u * 2 + 1][0]);
   t[u][1] = min(t[u * 2][1] , t[u * 2 + 1][1]);
}
void update(int u , int l , int r , int pos , long long x){
   if(l == r){
      if(x == -1LL){
         t[u][0] = 0LL;
         t[u][1] = (long long)1e9 + 1;
      }else{
         t[u][0] = x;
         t[u][1] = 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][0] = max(t[u * 2][0] , t[u * 2 + 1][0]);
   t[u][1] = min(t[u * 2][1] , t[u * 2 + 1][1]);
}
vector<long long> get(int u , int l , int r , int L , int R){
   if(l > r || r < L || l > R){
      return {0LL , (long long)1e9 + 1};
   }
   if(L <= l && r <= R){
      return t[u];
   }
   int m = (l + r) / 2;
   auto left = get(u * 2 , l , m , L , R);
   auto right = get(u * 2 + 1 , m + 1 , r , L , R);
   left[0] = max(left[0] , right[0]);
   left[1] = min(left[1] , right[1]);
   return left;
}
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[min(n , i + B[i])].push_back(i);
         turn_off[i + A[i] - 1].push_back(i);
      }
      if(i - A[i] >= 1){
         turn_on[i - A[i]].push_back(i);
         turn_off[max(0 , i - B[i] - 1)].push_back(i);
      }
   }
   cin >> q;
   int l1, rn;
   cin >> l1 >> rn;
   build(1 , 1 , n);
   long long ans = 0;
   for(int i = n;i >= 1;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] <= n){
         auto x = get(1 , 1 , n , i + A[i] , min(n , i + B[i]));
         ans = max({ans , x[0] - H[i] , H[i] - x[1]});
      }
   }
   cout << ans << endl;
}

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