Submission #1127704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127704		ntdaccode	Two Antennas (JOI19_antennas)	C++20	100 / 100	645 ms	58364 KiB

antennas

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 2e5 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;

int n, q, h[M], a[M], b[M];
int L[M], R[M];

int mi[4 * M], t[4 * M], lz[4 * M];

void lazy(int s)
{
  if(lz[s] == 0) return ;
  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 * 2] = max(lz[s],lz[s * 2]);
  lz[s * 2 + 1] = max(lz[s], lz[s * 2 + 1]);
  lz[s] = 0;
  return ;
}

void upd_point(int s,int l,int r,int pos,int val)
{
  if(l > pos || r < pos) return ;
  //cout << l << " " << r << " " << pos << "sa\n";
  if(l == r) {
    mi[s] = val;
    return ;
  }
  int mid = (l + r)/2;
  if(l != r && lz[s] != 0) lazy(s);
  upd_point(s * 2, l, mid, pos, val);
  upd_point(s * 2 + 1, mid + 1, r, pos, val);
  mi[s] = min(mi[s * 2], mi[s * 2 + 1]);
  t[s] = max({t[s],t[s * 2], t[s * 2 + 1]});
  //cout << t[s] << " ";
}


void upd_segment(int s,int l, int r,int u,int v,int val)
{
  if(l > v || u > r) return ;
  //cout << l << " " << r << " " << u << " " <<  v << "\n";
  if(u <= l && r <= v) {
      t[s] = max(t[s], val - mi[s]);
      //cout << t[s] << "\n";
      lz[s] = max(val, lz[s]);
      return ;
  }
  int mid = (l + r)/2;
  if(l != r && lz[s] != 0) lazy(s);
  upd_segment(s * 2, l, mid, u, v, val);
  upd_segment(s * 2 + 1, mid + 1, r, u, v, val);
  t[s] = max({t[s],t[s * 2], t[s * 2 + 1]});
  //cout << t[s] << " ";
}

int get(int s,int l,int r,int u,int v)
{
  if(l > v || r < u) return -1;
  //cerr << s << " " << t[s] << "\n";
  if(u <= l && r <= v) return t[s];
  int mid = (l + r)/2;
  if(l != r && lz[s] != 0) lazy(s);
  return max(get(s * 2, l, mid, u, v), get(s * 2 + 1, mid + 1, r, u, v));
}

vector<ii> add[M], Q[M];

void reset()
{
  for(int i = 1;i <= 4 * n; i++) {
    mi[i] = 2e9;
    t[i] =  -1;
    lz[i] = 0;
  }
  for(int i = 0;i <= n + 1; i++) add[i].clear();
}

int ans[M];
void process()
{

  for(int i = 1;i <= n; i++) {
    add[min(n + 1,i + a[i])].pb({i, h[i]});
    add[min(n + 1,i + b[i] + 1)].pb({i, 2e9});
    //cout << i << " " << min(n + 1,i + a[i]) << " " << min(n + 1,i + b[i] + 1) << "s\n";

    for(ii tmp : add[i]) {
      int idx = tmp.first, val = tmp.second;
      upd_point(1,1,n,idx,val);
    }

    upd_segment(1, 1, n, max(1ll, i - b[i]), max(0ll, i - a[i]), h[i]);
    //cout << i << " " << max(1ll, i - b[i]) << " " << max(0ll, i - a[i]) << "a\n";
    //cout << get(1,1,n,5,10) << "\n";


    for(ii tmp : Q[i]) {
      int l = tmp.first, idx = tmp.second;
      //cout << l << " " << i << " " << idx <<  " ";
      //cout << get(1,1,n,l,i) << " " << get_ans(1,1,n,l,i) << "\n";
      ans[idx] = max(ans[idx], get(1, 1, n, l, i));
    }

  }
}

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

  if(fopen("1.inp","r")) {
    freopen("1.inp","r",stdin);
    freopen("1.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];
  cin >> q;
  for(int i = 1;i <= q; i++) {
    cin >> L[i] >> R[i];
    Q[R[i]].pb({L[i], i});
    ans[i] = -1;
  }
  reset();
  process();
  reverse(h + 1,h + n + 1);
  reverse(a + 1,a + n + 1);
  reverse(b + 1,b + n + 1);
  for(int i = 1;i <= n; i++) Q[i].clear();
  for(int i = 1;i <= q; i++) {
      L[i] = n - L[i] + 1;
      R[i] = n - R[i] + 1;
      Q[L[i]].pb({R[i], i});
  }
  reset();
  process();
  for(int i = 1;i <= q; i++) cout << ans[i] << '\n';

}

Compilation message (stderr)

antennas.cpp: In function 'int32_t main()':
antennas.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
antennas.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
antennas.cpp:131:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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