제출 #1149436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149436		anmattroi	Two Antennas (JOI19_antennas)	C++20	0 / 100	428 ms	41628 KiB

antennas

#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, q;

inline constexpr void cmin(int &x, const int &y) {if (x > y) x = y;}
inline constexpr void cmax(int &x, const int &y) {if (x < y) x = y;}

struct TT {
    int h, a, b;
    TT() {}
    TT(int _h, int _a, int _b) : h(_h), a(_a), b(_b) {}
} tower[maxn];

int kq[maxn];
int rz[maxn];

struct node {
    int historic_max = -1, val = 0, lz = 0, sum = 0, lzsum = 0;
    node() {}
    node(int _historic_max, int _val, int _lz, int _sum, int _lzsum) : historic_max(_historic_max), val(_val), lz(_lz), sum(_sum), lzsum(_lzsum) {}
} st[4*maxn];

void up(int r) {
    cmax(st[r].historic_max, max(st[r<<1].historic_max, st[r<<1|1].historic_max));
    st[r].val = max(st[r<<1].val, st[r<<1|1].val);
    st[r].sum = st[r<<1].sum + st[r<<1|1].sum;
}
void apply(int r, int d, int e) {
    st[r].val += d;
    st[r].lz += d;
    if (st[r].sum) cmax(st[r].historic_max, st[r].val);
    st[r].sum += e;
    st[r].lzsum += e;
}

void down(int r) {
    apply(r<<1, st[r].lz, st[r].lzsum);
    apply(r<<1|1, st[r].lz, st[r].lzsum);
    st[r].lz = 0;
    st[r].lzsum = 0;
}

void update(int u, int v, int d, int e, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return;
    if (u <= lo && hi <= v) {
        apply(r, d, e);
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    update(u, v, d, e, r<<1, lo, mid);
    update(u, v, d, e, r<<1|1, mid+1, hi);
    up(r);
}


int get_max(int u, int v, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return -1;
    if (u <= lo && hi <= v) return st[r].historic_max;
    down(r);
    int mid = (lo + hi) >> 1;
    return max(get_max(u, v, r<<1, lo, mid), get_max(u, v, r<<1|1, mid+1, hi));
}

int get_sum(int u, int v, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return st[r].sum;
    down(r);
    int mid = (lo + hi) >> 1;
    return get_sum(u, v, r<<1, lo, mid) + get_sum(u, v, r<<1|1, mid+1, hi);
}

vector<ii> queryL[maxn], queryR[maxn];
vector<ii> nho[maxn];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> tower[i].h >> tower[i].a >> tower[i].b;


    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        queryL[l].emplace_back(r, i);
        queryR[r].emplace_back(l, i);
    }

    for (int i = 1; i <= q; i++) kq[i] = -1;

    for (int i = 1; i <= 4*n; i++) st[i] = node(-1, 0, 0, 0, 0);

    for (int r = 1; r <= n; r++) {
        for (auto [idx, type] : nho[r]) {
            if (type == 1) update(idx, idx, -tower[idx].h, 1);
            else update(idx, idx, tower[idx].h, -1);
        }

        auto [h, a, b] = tower[r];

        int p1 = max(r-b,1), p2 = r-a;
        if (p1 <= p2) update(p1, p2, h, 0);
        for (auto [l, idx] : queryR[r]) {
            cmax(kq[idx], get_max(l, r));
            rz[idx] += get_sum(l, r);
        }
        if (p1 <= p2) update(p1, p2, -h, 0);

        p1 = min(n+1, r+a); p2 = min(n+1, r+b+1);
        nho[p1].emplace_back(r, 1);
        nho[p2].emplace_back(r, 2);
    }
    for (int i = 0; i <= n+1; i++) nho[i].clear();

    for (int i = 1; i <= 4*n; i++) st[i] = node(-1, 0, 0, 0, 0);

    for (int l = n; l >= 1; l--) {
        for (auto [idx, type] : nho[l])
            if (type == 1) update(idx, idx, -tower[idx].h, 1);
            else update(idx, idx, tower[idx].h, -1);

        auto [h, a, b] = tower[l];

        int p1 = l+a, p2 = min(n, l+b);

        if (p1 <= p2) update(p1, p2, h, 0);

        for (auto [r, idx] : queryL[l])
            cmax(kq[idx], get_max(l, r));

        if (p1 <= p2) update(p1, p2, -h, 0);

        p1 = max(0, l-a); p2 = max(0, l-b-1);
        nho[p1].emplace_back(l, 1);
        nho[p2].emplace_back(l, 2);
    }

    for (int i = 1; i <= q; i++) cout << (rz[i] ? kq[i] : -1) << "\n";
}

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