Submission #627689

#	Time	Username	Problem	Language	Result	Execution time	Memory
627689		cadmiumsky	Two Antennas (JOI19_antennas)	C++17	100 / 100	1038 ms	43716 KiB

antennas

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

//#ifdef DLOCAL
//  #define cin fin
//  #define cout fout
//  ifstream cin(".in");
//  ofstream cout(".out");
//#endif

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5, inf = 1e9 + 5;
int rez[nmax];

int n, q;

namespace AINT {
  int rez[nmax * 4], back[nmax * 4], front[nmax * 4];
  
  void init(int node = 1, int cl = 0, int cr = n - 1) {
    rez[node] = -1;
    back[node] = inf;
    front[node] = -1;
    if(cl != cr) {
      int mid = cl + cr >> 1;
      init(2 * node, cl, mid);
      init(2 * node + 1, mid + 1, cr);
    }
    return;
  }
  
  void push(int node, bool push) {
    rez[node] = max(rez[node], front[node] - back[node]);
    if(push)
      front[2 * node] = max(front[node], front[2 * node]),
      front[2 * node + 1] = max(front[node], front[2 * node + 1]),
      front[node] = -1;
  }
  
  int query(int l, int r, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(r < cl || cr < l)
      return -1;
    if(l <= cl && cr <= r) {
      //cerr << "Query: " << cl << ' ' << cr << ' ' << back[node] << ' ' << rez[node] << '\n';
      return rez[node];
    }
    int mid = cl + cr >> 1;
    return max(query(l, r, 2 * node ,cl, mid), query(l, r, 2 * node + 1, mid + 1, cr));
  }
  
  void updback(int poz, int val, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(poz < cl || cr < poz)
      return;
    if(cl == cr) {
      front[node] = -1;
      back[node] = val;
      return;
    }
    int mid = cl + cr >> 1;
    updback(poz, val, 2 * node, cl, mid);
    updback(poz, val, 2 * node + 1, mid + 1, cr);
    back[node] = min(back[2 * node], back[2 * node + 1]);
    //cerr << cl << ' ' << cr << ' ' << back[node] << ' ' << rez[node] << '\n';
  }
  
  void updfront(int l, int r, int val, int node = 1, int cl = 0, int cr = n - 1) {
    push(node, cl != cr);
    if(r < cl || cr < l)
      return;
    
    if(l <= cl && cr <= r) {
      front[node] = val;
      //cerr << "AddFront: " << cl << ' ' << cr << ' ' << val << ' ' << back[node] << '\n';
      push(node, cl != cr);
      //cerr << "AddFront: " << cl << ' ' << cr << ' ' << val << ' ' << back[node] << ' ' << rez[node] << '\n';
      return;
    }
    
    int mid = cl + cr >> 1;
    updfront(l, r, val, 2 * node, cl, mid);
    updfront(l, r, val, 2 * node + 1, mid + 1, cr);
    rez[node] = max(rez[2 * node], rez[2 * node + 1]);
    //cerr << cl << ' ' << cr << ' ' << rez[node] << '\n';
  }
}

vector<pii> qsevents[nmax];
vector<int> antevents[nmax]; 
void solve(vector<tii> ant, vector<pii> qs) {
  AINT::init(); 
  for(int i = 0; i < n; i++) {
    qsevents[i].clear();
    antevents[i].clear();
  }
  
  //for(auto [l, r] : qs)
    //cout << l << ' ' << r << '\n';
  
  for(int A, B, H, i = 0; i < n; i++) {
    tie(A, B, H) = ant[i];
    
    if(i - A >= 0)	
      antevents[i - A].emplace_back(i);
    if(i - B > 0)	
      antevents[i - B - 1].emplace_back(-i - 1);
  }
  int ind = 0;
  for(auto [l, r] : qs)
    qsevents[l].emplace_back(r, ind),
    ind++;
  
  for(int A, B, H, i = n - 1; i >= 0; i--) {
    tie(A, B, H) = ant[i];
    
    for(auto x : antevents[i]) {
      if(x >= 0)
	//cerr << "+ " << x << ' ' << get<2>(ant[x]) << '\n',
	AINT::updback(x, get<2>(ant[x]));
      else {
	//cerr << "+ " << x + 1 << '\n';
	x = -(x + 1);
	AINT::updback(x, inf);
      } 
    }
    
    //cerr << H << ' ' << i + A << ' ' << i + B << '\n';
    AINT::updfront(i + A, i + B, H);
  
    for(auto [r, idx] : qsevents[i]) {
      rez[idx] = max(rez[idx], AINT::query(i, r));
    }
  }
  
  return;
}

signed main() {
  vector<tii> ant;
  vector<pii> qs;
  cin >> n;
  ant.resize(n);
  for(auto &[a, b, h] : ant)
    cin >> h >> a >> b;
  
  cin >> q;
  for(int i = 0; i < q; i++) rez[i] = -1;
  qs.resize(q);
  for(auto &[l, r] : qs)
    cin >> l >> r,
    --l,
    --r;
  
  solve(ant, qs);
  
  reverse(ant.begin(), ant.end());
  for(auto &[l, r] : qs)
    l = n - l - 1,
    r = n - r - 1,
    swap(l, r);
  solve(ant, qs);
  
  for(int i = 0; i < q; i++)
    cout << rez[i] << '\n';
  return 0;
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message (stderr)

antennas.cpp: In function 'void AINT::init(int, int, int)':
antennas.cpp:32:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
antennas.cpp: In function 'int AINT::query(int, int, int, int, int)':
antennas.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
antennas.cpp: In function 'void AINT::updback(int, int, int, int, int)':
antennas.cpp:68:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
antennas.cpp: In function 'void AINT::updfront(int, int, int, int, int, int)':
antennas.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

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