Submission #200958

#	Time	Username	Problem	Language	Result	Execution time	Memory
200958		qkxwsm	Two Antennas (JOI19_antennas)	C++14	100 / 100	1186 ms	49528 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, ll> ppl;

const int MAXN = 200013;
const int INF = 1000000007;
const ll LLINF = 2696969696969696969ll;

int N, Q;
pair<ll, pii> arr[MAXN];
pii queries[MAXN];
vi born[MAXN], dead[MAXN];
ll ans[MAXN];
vpi quer[MAXN];

ppl seg[3 * MAXN];

void push(int w, int L, int R)
{
    if (L != R)
    {
        ckmax(seg[w << 1].fi.se, seg[w].fi.se);
        ckmax(seg[w << 1 | 1].fi.se, seg[w].fi.se);
    }
    ckmax(seg[w].se, seg[w].fi.fi + seg[w].fi.se);
    seg[w].fi.se = -LLINF;
    return;
}
void build(int w, int L, int R)
{
    seg[w] = {{-LLINF, -LLINF}, -2 * LLINF};
    if (L == R)
    {
        return;
    }
    int mid = (L + R) >> 1;
    build(w << 1, L, mid);
    build(w << 1 | 1, mid + 1, R);
}
void update(int w, int L, int R, int a, ll v)
{
    push(w, L, R);
    if (a < L || R < a) return;
    if (L == R)
    {
        seg[w].fi.fi = v;
        seg[w].fi.se = -LLINF;
        // seg[w].se = seg[w].fi.fi + seg[w].fi.se;
        return;
    }
    int mid = (L + R) >> 1;
    update(w << 1, L, mid, a, v);
    update(w << 1 | 1, mid + 1, R, a, v);
    seg[w].fi.fi = max(seg[w << 1].fi.fi, seg[w << 1 | 1].fi.fi);
    seg[w].se = max(seg[w << 1].se, seg[w << 1 | 1].se);
    return;
}
void rangeupdate(int w, int L, int R, int a, int b, ll v)
{
    // if (w == 1) cerr << L << ' ' << R << ' ' << a << ' ' << b << endl;
    push(w, L, R);
    if (b < L || R < a) return;
    if (a <= L && R <= b)
    {
        ckmax(seg[w].fi.se, v);
        push(w, L, R);
        // cerr << seg[w].fi.fi << ' ' << seg[w].fi.se << ' ' << seg[w].se << endl;
        return;
    }
    int mid = (L + R) >> 1;
    rangeupdate(w << 1, L, mid, a, b, v);
    rangeupdate(w << 1 | 1, mid + 1, R, a, b, v);
    seg[w].fi.fi = max(seg[w << 1].fi.fi, seg[w << 1 | 1].fi.fi);
    seg[w].se = max(seg[w << 1].se, seg[w << 1 | 1].se);
    return;
}
ll query(int w, int L, int R, int a, int b)
{
    push(w, L, R);
    if (a <= L && R <= b)
    {
        // cerr << seg[w].fi.fi << ' ' << seg[w].fi.se << ' ' << seg[w].se << endl;
        return seg[w].se;
    }
    int mid = (L + R) >> 1;
    if (b <= mid) return query(w << 1, L, mid, a, b);
    if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
    return max(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}

void solve()
{
    build(1, 0, N - 1);
    FOR(i, 0, N)
    {
        for (int x : born[i])
        {
            update(1, 0, N - 1, x, -arr[x].fi);
            // cerr << "setfi " << x << ' ' << -arr[x].fi << endl;
        }
        for (int x : dead[i])
        {
            update(1, 0, N - 1, x, -LLINF);
            // cerr << "setfi " << x << ' ' << -LLINF << endl;
        }
        int lt = max(0, i - arr[i].se.se), rt = i - arr[i].se.fi;
        if (lt <= rt)
        {
            rangeupdate(1, 0, N - 1, lt, rt, arr[i].fi);
            // cerr << "setse " << lt << ' ' << rt << ' ' << arr[i].fi << endl;
        }
        for (pii p : quer[i])
        {
            auto res = query(1, 0, N - 1, p.fi, i);
            // cerr << "ask " << p.fi << " " << i << " " << res << endl;
            ckmax(ans[p.se], res);
        }
    }
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    FOR(i, 0, N)
    {
        cin >> arr[i].fi >> arr[i].se.fi >> arr[i].se.se;
    }
    cin >> Q;
    FOR(i, 0, Q)
    {
        cin >> queries[i].fi >> queries[i].se;
        queries[i].fi--; queries[i].se--;
        quer[queries[i].se].PB({queries[i].fi, i});
        ans[i] = -1;
    }
    FOR(i, 0, N)
    {
        if (i + arr[i].se.fi < N)
        {
            born[i + arr[i].se.fi].PB(i);
        }
        if(i + arr[i].se.se + 1 < N)
        {
            dead[i + arr[i].se.se + 1].PB(i);
        }
    }
    solve();
    FOR(i, 0, N)
    {
        arr[i].fi = INF - arr[i].fi;
    }
    solve();
    FOR(i, 0, Q)
    {
        cout << ans[i] << '\n';
    }
    return 0;
}

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