Submission #1100622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100622		VinhLuu	Two Antennas (JOI19_antennas)	C++17	100 / 100	585 ms	38296 KiB

antennas

#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define all(vin) vin.begin(), vin.end()
using namespace std;

const int N = 2e5 + 2;
const int oo = 1e9 + 1;

int n, h[N], a[N], b[N], kq[N], st[N << 2], T[N << 2], lz[N << 2];
vector<pair<int,int>> open[N], Q[N];

void dolz(int i){
  if(lz[i] == 0) return;
  int x = lz[i]; lz[i] = 0;
  T[i << 1] = max(T[i << 1], x - st[i << 1]);
  T[i << 1|1] = max(T[i << 1|1], x - st[i << 1|1]);
  lz[i << 1] = max(lz[i << 1], x);
  lz[i << 1|1] = max(lz[i << 1|1], x);
}

void change(int i,int l,int r,int u,int val){
  if(l > r || r < u || u < l) return;
  if(l == r){
    st[i] = val;
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  change(i << 1, l, mid, u, val);
  change(i << 1|1, mid + 1, r, u, val);
  st[i] = min(st[i << 1], st[i << 1|1]);
  T[i] = max(T[i << 1], T[i << 1|1]);
}

void update(int i,int l,int r,int u,int v,int val){
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v){
    T[i] = max(T[i], val - st[i]);
    lz[i] = max(lz[i], val);
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, v, val);
  update(i << 1|1, mid + 1, r, u, v, val);
  st[i] = min(st[i << 1], st[i << 1|1]);
  T[i] = max(T[i << 1], T[i << 1|1]);
}

int get(int i,int l,int r,int u,int v){
  if(l > r || r < u || v < l) return -1;
  if(u <= l && r <= v) return T[i];
  dolz(i);
  int mid = (l + r) / 2;
  return max(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
}

void solve(){
  for(int i = 1; i <= 4 * n; i ++) st[i] = oo, T[i] = -1, lz[i] = 0;
  for(int i = 1; i <= n; i ++){
//    cerr << "            " << i << " phase\n";
    for(auto [j, w] : open[i]){
      if(w == 1){
//        cerr << j << " " << h[j] << " up\n";
        change(1, 1, n, j, h[j]);
      }else{
//        cerr << j << " " << oo << " clear\n";
        change(1, 1, n, j, oo);
      }
    }

    if(i - a[i] >= 1){
//      cerr << max(1, i - b[i]) << " " << i - a[i] << " " << h[i] << " ans\n";
      update(1, 1, n, max(1, i - b[i]), i - a[i], h[i]);
    }
    for(auto [l, id] : Q[i]){
      int tmp = get(1, 1, n, l, i);
//      cerr << id << " " << l << " " << tmp << " g\n";
      kq[id] = max(kq[id], get(1, 1, n, l, i));
    }
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n;
  for(int i = 1; i <= n; i ++){
    cin >> h[i] >> a[i] >> b[i];
    if(i + a[i] <= n){
      open[i + a[i]].push_back({i, 1});
    }
    if(i + b[i] + 1 <= n){
      open[i + b[i] + 1].push_back({i, -1});
    }
  }
  int q; cin >> q;
  for(int i = 1; i <= q; i ++){
    kq[i] = -1;
    int l, r; cin >> l >> r;
    Q[r].push_back({l, i});
  }
  solve();
//  cerr << " end 1\n";
  for(int i = 1; i <= n; i ++) h[i] = oo - h[i];
  solve();
  for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}

Compilation message (stderr)

antennas.cpp: In function 'void solve()':
antennas.cpp:78:11: warning: unused variable 'tmp' [-Wunused-variable]
   78 |       int tmp = get(1, 1, n, l, i);
      |           ^~~
antennas.cpp: In function 'int main()':
antennas.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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