Submission #1012661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012661		otarius	Two Antennas (JOI19_antennas)	C++17	100 / 100	311 ms	50512 KiB

antennas

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <iomanip>
using namespace std;

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long

// #define int long long
// #define int unsigned long long

const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;

vector<int> ins[200005], ers[200005];
struct node {
    int lmax, lmin, rmax, rmin, ans;
} t[2000040];
bool comp(pair<pii, int> a, pair<pii, int> b) {
    return a.ff.sc < b.ff.sc;
}
void build(int v, int tl, int tr) {
    t[v].ans = -1;
    t[v].lmin = t[v].rmin = inf;
    t[v].lmax = t[v].rmax = -inf;
    if (tl == tr) return;
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
}
void prop(int v) {
    if (t[v].rmax < 0) return;
    t[2 * v].rmin = min(t[2 * v].rmin, t[v].rmin);
    t[2 * v].rmax = max(t[2 * v].rmax, t[v].rmax);
    t[2 * v + 1].rmin = min(t[2 * v + 1].rmin, t[v].rmin);
    t[2 * v + 1].rmax = max(t[2 * v + 1].rmax, t[v].rmax);
    t[v].rmin = inf; t[v].rmax = -inf;
    t[2 * v].ans = max({t[2 * v].ans, t[2 * v].lmax - t[2 * v].rmin, t[2 * v].rmax - t[2 * v].lmin});
    t[2 * v + 1].ans = max({t[2 * v + 1].ans, t[2 * v + 1].lmax - t[2 * v + 1].rmin, t[2 * v + 1].rmax - t[2 * v + 1].lmin});
}
void update1(int v, int tl, int tr, int pos, int val) {
    prop(v);
    if (tl == tr) {
        t[v].lmax = t[v].lmin = val;
        return;
    } int tm = (tl + tr) / 2;
    if (pos <= tm) update1(2 * v, tl, tm, pos, val);
    else update1(2 * v + 1, tm + 1, tr, pos, val);
    t[v].lmin = min(t[2 * v].lmin, t[2 * v + 1].lmin);
    t[v].lmax = max(t[2 * v].lmax, t[2 * v + 1].lmax);
}
void erase(int v, int tl, int tr, int pos) {
    if (tl == tr) { 
        t[v].lmin = inf;
        t[v].lmax = -inf;
        return;
    } prop(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) erase(2 * v, tl, tm, pos);
    else erase(2 * v + 1, tm + 1, tr, pos);
    t[v].lmin = min(t[2 * v].lmin, t[2 * v + 1].lmin);
    t[v].lmax = max(t[2 * v].lmax, t[2 * v + 1].lmax);
}
void update2(int v, int tl, int tr, int l, int r, int val) {
    if (r < tl || tr < l) return;
    prop(v);
    if (l <= tl && tr <= r) {
        t[v].rmin = t[v].rmax = val;
        t[v].ans = max({t[v].ans, t[v].rmax - t[v].lmin, t[v].lmax - t[v].rmin});
        return;
    } int tm = (tl + tr) / 2;
    update2(2 * v, tl, tm, l, min(r, tm), val);
    update2(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
    t[v].ans = max(t[2 * v].ans, t[2 * v + 1].ans);
}
int getmax(int v, int tl, int tr, int l, int r) {
    if (l > r) return -1;
    prop(v);
    if (tl == l && tr == r)
        return t[v].ans;
    int tm = (tl + tr) / 2;
    return max(getmax(2 * v, tl, tm, l, min(r, tm)),
               getmax(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
void solve() {
    int n, q;
    cin >> n;
    int h[n + 1], a[n + 1], b[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
        if (i + a[i] <= n) ins[i + a[i]].pb(i);
        if (i + b[i] + 1 <= n) ers[i + b[i] + 1].pb(i);
    } cin >> q;
    build(1, 1, n);
    int ans[q + 1];
    vector<pair<pii, int>> qr(q);
    for (int i = 0; i < q; i++) {
        cin >> qr[i].ff.ff >> qr[i].ff.sc; qr[i].sc = i + 1;
    } sort(qr.begin(), qr.end(), comp);
    for (int i = 1, j = 0; i <= n; i++) {
        for (int v : ins[i])
            update1(1, 1, n, v, h[v]);
        for (int v : ers[i])
            erase(1, 1, n, v);
        if (i - a[i] >= 1)
            update2(1, 1, n, max(1, i - b[i]), i - a[i], h[i]);
        while (qr[j].ff.sc == i) {
            ans[qr[j].sc] = getmax(1, 1, n, qr[j].ff.ff, qr[j].ff.sc); j++;
        }
    } for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

/*
-1
-1
828818552
-1
-1
958376243
-1
736480018
-1
-1
-1
828818552
648812417
648812417
-1
-1
736480018
-1
-1
-1
828818552
-1
828818552
828818552
609416339
350445999
828818552
-1
-1
828818552
557668751
864679211
-1
-1
828818552
736480018
828818552
-1
-1
-1
648812417
828818552
828818552
-1
736480018
-1
-1
828818552
866724750
-1
828818552
155328180
828818552
746880959
828818552
-1
736480018
761492920
746880959
-1
-1
736480018
-1
-1
-1
853810512
-1
209493436


*/

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