Submission #816811

#	Time	Username	Problem	Language	Result	Execution time	Memory
816811		Cookie	Two Antennas (JOI19_antennas)	C++14	100 / 100	630 ms	77452 KiB

antennas

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9 + 5, mxv = 1005, mxn = 4e5 + 5;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
ll h[mxn + 1], a[mxn + 1], b[mxn + 1];
ll mxval[4 * mxn + 1], mnval[4 * mxn + 1], mxupd[4 * mxn + 1], mnupd[4 * mxn + 1], res[4 * mxn + 1], ans[mxn + 1];
vt<pii>queries[mxn + 1], comp[mxn + 1];
void change(int nd, ll mx, ll mn){
    mxupd[nd] = max(mxupd[nd], mx); mnupd[nd] = min(mnupd[nd], mn);
    res[nd] = max(res[nd], mxupd[nd] - mnval[nd]);
    res[nd] = max(res[nd], mxval[nd] - mnupd[nd]);
}
void push(int nd){
    ll mx = mxupd[nd], mn = mnupd[nd];
    change(nd << 1, mx, mn); change(nd << 1 | 1, mx, mn);
    mxupd[nd] = -inf; mnupd[nd] = inf;
}
void updsingle(int nd, int l, int r, int id, ll mn, ll mx){
    if(id < l || id > r)return;
    if(l == r){
        mxval[nd] = mx; mnval[nd] = mn; mxupd[nd] = -inf; mnupd[nd] = inf;
        return;
    }
    push(nd);
    int mid = (l + r) >> 1;
    updsingle(nd << 1, l, mid, id, mn, mx); updsingle(nd << 1 | 1, mid + 1, r, id, mn, mx);
    mnval[nd] = min(mnval[nd << 1], mnval[nd << 1 | 1]);
    mxval[nd] = max(mxval[nd << 1], mxval[nd << 1 | 1]);
 }
 void updrange(int nd, int l, int r, int ql, int qr, int v){
     if(ql > r || qr < l)return;
     if(ql <= l && qr >= r){
         change(nd, v, v);
         return;
     }
    int mid = (l + r) >> 1;
    push(nd);
    updrange(nd << 1, l, mid, ql, qr, v); updrange(nd << 1 | 1, mid + 1, r, ql, qr, v);
    res[nd] = max(res[nd << 1], res[nd << 1 | 1]);
 }
int get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(-1);
    if(ql <= l && qr >= r)return(res[nd]);
    push(nd);
    int mid = (l + r) >> 1;
    return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> h[i] >> a[i] >> b[i];
    for(int i = 1; i <= 4 * n; i++){
        res[i] = -1; mxval[i] = mxupd[i] = -inf; mnval[i] = mnupd[i] = inf;
    }
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        queries[r].pb(make_pair(l, i));
    }
    for(int i = 1; i <= n; i++){
        for(auto [type, id]: comp[i]){
            if(type == 1){
                updsingle(1, 1, n, id, h[id], h[id]);
            }else{
                updsingle(1, 1, n, id, inf, -inf);
            }
            
        }
        if(i - a[i] >= 1)updrange(1, 1, n, max(i - b[i], (ll)1), i - a[i], h[i]);
        for(auto [l, id]: queries[i]){
            ans[id] = get(1, 1, n, l, i);
        }
        comp[i + a[i]].pb(make_pair(1, i)); comp[i + b[i] + 1].pb(make_pair(-1, i));
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    return(0);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         for(auto [type, id]: comp[i]){
      |                  ^
antennas.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         for(auto [l, id]: queries[i]){
      |                  ^

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