Submission #1128298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128298		duyhoanho	Two Antennas (JOI19_antennas)	C++20	0 / 100	319 ms	39176 KiB

antennas

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N = 2e5 + 10, oo = 1e17;
int n, h[N], q, a[N], b[N], ans[N], mi[4 * N], lz[4 * N], t[4 * N];
pii que[N];
vector<int> st[N], ed[N];
struct querry{
  int l, id;
};
vector<querry> R[N];

void push(int s){
  if(!lz[s]) return;
  lz[s * 2] = max(lz[s * 2], lz[s]);
  lz[s * 2 + 1] = max(lz[s * 2 + 1], lz[s]);
  t[s * 2] = max(t[s * 2], lz[s] - mi[s * 2]);
  t[s * 2 + 1] = max(t[s * 2 + 1], lz[s] - mi[s * 2 + 1]);
  lz[s] = 0;
}

void build(int s, int l, int r){
  if(l == r){
    mi[s] = oo;
    t[s] = -1;
    lz[s] = 0;
    return;
  }
  int mid = (l + r) / 2;
  build(s * 2, l, mid);
  build(s * 2 + 1, mid + 1, r);
  lz[s] = 0;
  t[s] = -1;
  mi[s] = min(mi[s * 2], mi[s * 2 + 1]);
}

void up_min(int s, int l, int r, int i, int val){
  if(i < l || r < i) return;
  if(l == r){
    mi[s] = val;
    return;
  }
  int mid = (l + r) / 2;
  push(s);
  up_min(s * 2, l, mid, i, val);
  up_min(s * 2 + 1, mid + 1, r, i, val);
  mi[s] = min(mi[s * 2], mi[s * 2 + 1]);
}

void up(int s, int l, int r, int u, int v, int val){
  if(r < u || v < l) return;
  if(u <= l && r <= v){
    t[s] = max(t[s], val - mi[s]);
    lz[s] = val;
    return;
  }
  int mid = (l + r) / 2;
  push(s);
  up(s * 2, l, mid, u, v, val);
  up(s * 2 + 1, mid + 1, r, u, v, val);
  t[s] = max(t[s * 2], t[s * 2 + 1]);
}

int get(int s, int l, int r, int u, int v){
  if(r < u || v < l) return -1;
  if(u <= l && r <= v) return t[s];
  int mid = (l + r) / 2;
  if(l != r) push(s);
  return max(get(s * 2, l, mid, u, v), get(s * 2 + 1, mid + 1, r, u, v));
}

int get_min(int s, int l, int r, int u, int v){
  if(r < u || v < l) return oo;
  if(u <= l && r <= v) return mi[s];
  int mid = (l + r) / 2;
  if(l != r) push(s);
  return min(get_min(s * 2, l, mid, u, v), get_min(s * 2 + 1, mid + 1, r, u, v));
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  if(fopen("task.inp","r")){
      freopen("task.inp","r",stdin);
      freopen("task.out","w",stdout);
  }
  #define task ""
  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];
      st[min(i + a[i], n + 1)].push_back(i);
      ed[min(i + b[i], n) + 1].push_back(i);
  }
  cin >> q;
  for(int i = 1; i <= q; i++){
    int l, r;
    cin >> l >> r;
    que[i] = {l, r};
    ans[i] = -1;
    R[r].push_back({l, i});
  }
  build(1, 1, n + 1);
  for(int i = 2; i <= n; i++){
    for(int v : st[i]) up_min(1, 1, n + 1, v, h[v]);
    for(int v : ed[i]) up_min(1, 1, n + 1, v, oo);
    if(i - a[i] > 0) up(1, 1, n + 1, max(i - b[i], 1ll), max(i - a[i], 1ll), h[i]);
    for(auto [l, id] : R[i]){
      ans[id] = get(1, 1, n + 1, l, i);
    }
  }

  for(int i = 1; i <= n; i++){
    st[i].clear();
    ed[i + 1].clear();
    R[i].clear();
  }
  st[n + 1].clear();

  int it = n;
  for(int i = 1; i <= (n + 1) / 2; i++){
    swap(a[i], a[it]);
    swap(b[i], b[it]);
    swap(h[i], h[it]);
    it--;
  }
  for(int i = 1; i <= n; i++){
    st[min(i + a[i], n + 1)].push_back(i);
    ed[min(i + b[i], n) + 1].push_back(i);
  }
  //for(int i = 1; i <= n; i++) cout<<h[i]<<" "<<a[i]<<" "<<b[i]<<"\n";

  for(int i = 1; i <= q; i++){
    auto[x , y] = que[i];
    int l = n - y + 1;
    int r = n - x + 1;
   // cerr<<l<<" "<<r<<"\n";
    R[r].push_back({l, i});
  }

  //for(int i = 1; i <= n; i++) cout<<h[i]<<" "<<a[i]<<" "<<b[i]<<"\n";

  build(1, 1, n + 1);
  for(int i = 2; i <= n; i++){
    for(int v : st[i]) up_min(1, 1, n + 1, v, h[v]);
    for(int v : ed[i]) up_min(1, 1, n + 1, v, oo);
    if(i - a[i] > 0) up(1, 1, n + 1, max(i - b[i], 1ll), max(i - a[i], 1ll), h[i]);
//    cerr<<get(1, 1, n + 1, 1, 1)<<" "<<i<<"\n";
    for(auto [l, id] : R[i]){
//      for(int j = 1; j <= n; j++) cerr<<get(1, 1, n + 1, j, j)<<" ";
      ans[id] = max(ans[id], get(1, 1, n + 1, l, i));
    }
  }
  for(int i = 1; i <= q; i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

antennas.cpp: In function 'int32_t main()':
antennas.cpp:89:14: 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:14: 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);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:94:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:95:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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