Submission #1170354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170354		M_W_13	Two Antennas (JOI19_antennas)	C++20	100 / 100	473 ms	37364 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 18;
const ll INF = 1e17;
ll maks[2 * MAXN][2];
ll wyn[2 * MAXN][2];
ll kopnij[2 * MAXN][2];

void kopnij_w_dol(int v, int c) {
    kopnij[2 * v][c] = max(kopnij[2 * v][c], kopnij[v][c]);
    kopnij[2 * v + 1][c] = max(kopnij[2 * v + 1][c], kopnij[v][c]);
    wyn[2 * v][c] = max(wyn[2 * v][c], kopnij[2 * v][c] + maks[2 * v][c]);
    wyn[2 * v + 1][c] = max(wyn[2 * v + 1][c], kopnij[2 * v + 1][c] + maks[2 * v + 1][c]);
    kopnij[v][c] = -INF;
}

void upd(int c, int v, int l, int r, int p, int k, ll x) {
    if (p <= l && r <= k) {
        kopnij[v][c] = max(kopnij[v][c], x);
        wyn[v][c] = max(wyn[v][c], maks[v][c] + x);
    }
    else if (p > r || l > k) {

    }
    else {
        kopnij_w_dol(v, c);
        int sr = (l + r)/2;
        upd(c, 2 * v, l, sr, p, k, x);
        upd(c, 2 * v + 1, sr + 1, r, p, k, x);
        wyn[v][c] = max(wyn[v][c], max(wyn[2 * v][c], wyn[2 * v + 1][c]));
    }
}

void upd2(int c, int v, int l, int r, int p, int k, ll x) {
    if (p <= l && r <= k) {
        maks[v][c] = x;
        kopnij[v][c] = -INF;
    }
    else if (p > r || l > k) {

    }
    else {
        kopnij_w_dol(v, c);
        int sr = (l + r)/2;
        upd2(c, 2 * v, l, sr, p, k, x);
        upd2(c, 2 * v + 1, sr + 1, r, p, k, x);
        maks[v][c] = max(maks[2 * v][c], maks[2 * v + 1][c]);
        wyn[v][c] = max(wyn[v][c], max(wyn[2 * v][c], wyn[2 * v + 1][c]));
    }
}

ll query(int c, int v, int l, int r, int p, int k) {
    if (p <= l && r <= k) {
        return wyn[v][c];
    }
    else if (p > r || l > k) {
        return -1;
    }
    else {
        kopnij_w_dol(v, c);
        int sr = (l + r)/2;
        return max(query(c, 2 * v, l, sr, p, k), query(c, 2 * v + 1, sr + 1, r, p, k));
    }
}

struct ant {
    ll h;
    int a, b;
};

ant T[MAXN];

struct ask {
    int l, r;
    int nr;
};

bool por(ask a, ask b) {
    return a.r < b.r;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    rep(i, 2 * MAXN) {
        rep(c, 2) {
            kopnij[i][c] = -INF;
            wyn[i][c] = -INF;
            maks[i][c] = -INF;
        }
    }
    int n;
    cin >> n;
    rep(i, n) {
        cin >> T[i].h >> T[i].a >> T[i].b;
    }
    int q;
    cin >> q;
    ask pyt[q];
    ll odp[q];
    rep(i, q) {
        odp[i] = -1;
        cin >> pyt[i].l >> pyt[i].r;
        pyt[i].l--;
        pyt[i].r--;
        pyt[i].nr = i;
    }
    sort(pyt, pyt + q, por);
    vector<pair<int, int>> zmiany;
    bool czyjest[n];
    rep(i, n) {
        czyjest[i] = false;
        zmiany.pb({i + T[i].a, i});
        zmiany.pb({i + T[i].b + 1, i});
    }
    sort(zmiany.begin(), zmiany.end());
    int it = 0;
    int sz = zmiany.size();
    int it2 = 0;
    rep(i, n) {
        while (it < sz && zmiany[it].st <= i) {
            int v = zmiany[it].nd;
            if (!czyjest[v]) {
                upd2(0, 1, 0, MAXN - 1, v, v, -T[v].h);
                upd2(1, 1, 0, MAXN - 1, v, v, T[v].h);
                czyjest[v] = true;
            }
            else {
                upd2(0, 1, 0, MAXN - 1, v, v, -INF);
                upd2(1, 1, 0, MAXN - 1, v, v, -INF);
                czyjest[v] = false;
            }
            it++;
        }
        int l = i - T[i].b;
        int r = i - T[i].a;
        if (r >= 0) {
            l = max(0, l);
            upd(0, 1, 0, MAXN - 1, l, r, T[i].h);
            upd(1, 1, 0, MAXN - 1, l, r, -T[i].h);
        }
        // cout << maks[1][0] << " " << maks[1][1] << '\n';
        // cout << wyn[1][0] << " " << wyn[1][1] << '\n';
        // cout << "i = " << i << " query = " << query(0, 1, 0, MAXN - 1, 0, i) << " " << query(1, 1, 0, MAXN - 1, 0, i) << '\n';
        while (it2 < q && pyt[it2].r <= i) {
            odp[pyt[it2].nr] = max(odp[pyt[it2].nr], max(query(0, 1, 0, MAXN - 1, pyt[it2].l, pyt[it2].r), query(1, 1, 0, MAXN - 1, pyt[it2].l, pyt[it2].r)));
            it2++;
        }
    }
    rep(i, q) {
        cout << odp[i] << " ";
    }
    cout << '\n';
    return 0;
}

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