제출 #1308486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308486		vako_p	Two Antennas (JOI19_antennas)	C++20	22 / 100	188 ms	26420 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,q,a[mxN],b[mxN],h[mxN];

bool check(ll i, ll j){
  return (j <= i + b[i] and j >= i + a[i] and i >= j - b[j] and i <= j - a[j]);
}

struct segtree{
  vector<ll> v;
  ll sz = 1;

  void init(){
    while(sz < n + 5) sz *= 2;
    v.assign(2 * sz, -2e9);
  }

  void set(ll val, ll i, ll x, ll lx, ll rx){
    if(rx - lx == 1){
      v[x] = val;
      return;
    }
    ll mid = lx + (rx - lx) / 2;
    if(i < mid) set(val, i, 2 * x + 1, lx, mid);
    else set(val, i, 2 * x + 2, mid, rx);
    v[x] = max(v[2 * x + 1], v[2 * x + 2]);
  }

  void set(ll val, ll i){
    set(val, i, 0, 0, sz);
  }

  ll find(ll l, ll r, ll x, ll lx, ll rx){
    if(lx >= r or rx <= l) return -2e9;
    if(lx >= l and rx <= r) return v[x];
    ll mid = lx + (rx - lx) / 2;
    return max(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx));
  }

  ll find(ll l, ll r){
    return find(l, r, 0, 0, sz);
  }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n;
  vector<vector<ll>> v(n + 5),v1(n + 5);
  for(int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
  for(int i = 1; i <= n; i++){
    if(i + a[i] <= n) v[i + a[i]].pb(i);
    if(i + b[i] + 1 <= n) v1[i + b[i] + 1].pb(i);
  }
  segtree s,s1;
  s.init();
  s1.init();
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    for(auto it : v[i]){
      s.set(h[it], it);
      s1.set(-h[it], it);
    }
    for(auto it : v1[i]){
      s.set(0, it);
      s1.set(-2e9, it);
    }
    ll r = max(1LL, i - a[i] + 1),l = max(1LL, i - b[i]);
    ans = max(ans, s.find(l, r) - h[i]);
    // debug(s1.find(l, r));
    ans = max(ans, h[i] + s1.find(l, r));
  }
  cout << ans << '\n';
}

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