Submission #583132

#	Time	Username	Problem	Language	Result	Execution time	Memory
583132		Lucpp	Two Antennas (JOI19_antennas)	C++17	100 / 100	947 ms	35456 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+1;
const int MAX = 2e5;
const int cap = 1<<18;

struct Data{
    int val = -INF, hmin = INF;
};
Data combine(Data a, Data b){
    return {max(a.val, b.val), min(a.hmin, b.hmin)};
}

Data S[2*cap];
int O[2*cap];
bool lazy[2*cap];

void init(){
    memset(lazy, 0, sizeof(lazy));
    fill_n(O, 2*cap, -INF);
    fill_n(S, 2*cap, Data());
}
void apply(int i, int u){
    S[i].val = max(S[i].val, u-S[i].hmin);
    O[i] = max(O[i], u);
    lazy[i] = true;
}
void push(int i){
    if(lazy[i]){
        apply(2*i, O[i]);
        apply(2*i+1, O[i]);
        O[i] = -INF;
        lazy[i] = false;
    }
}
void update(int l, int r, int u, int a = 1, int b = cap, int i = 1){
    if(l <= a && b <= r) apply(i, u);
    else if(b < l || r < a);
    else{
        push(i);
        int m = (a+b)/2;
        update(l, r, u, a, m, 2*i);
        update(l, r, u, m+1, b, 2*i+1);
        S[i] = combine(S[2*i], S[2*i+1]);
    }
}
void updH(int p, int h, int a = 1, int b = cap, int i = 1){
    if(a == b){
        S[i].hmin = h;
        return;
    }
    push(i);
    int m = (a+b)/2;
    if(p <= m) updH(p, h, a, m, 2*i);
    else updH(p, h, m+1, b, 2*i+1);
    S[i] = combine(S[2*i], S[2*i+1]);
}
Data qry(int l, int r, int a = 1, int b = cap, int i = 1){
    if(l <= a && b <= r) return S[i];
    if(b < l || r < a) return Data();
    push(i);
    int m = (a+b)/2;
    return combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}


int N, Q;
int A[MAX], B[MAX], H[MAX], ans[MAX];
vector<pair<int, int>> todo[MAX], queries[MAX];

void solve(){
    init();
    for(int R = 0; R < N; R++){
        for(auto [i, op] : todo[R]) {
            if(op == 1) updH(i+1, H[i]);
            else updH(i+1, INF);
        }
        if(R-A[R] >= 0){
            int l = max(0, R-B[R]), r = R-A[R];
            update(l+1, r+1, H[R]);
        }
        for(auto [L, ind] : queries[R]){
            ans[ind] = max(ans[ind], qry(L+1, R+1).val);
        }
    }
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> H[i] >> A[i] >> B[i];
        if(i+A[i] < N) todo[i+A[i]].emplace_back(i, 1);
        if(i+B[i]+1 < N) todo[i+B[i]+1].emplace_back(i, -1);
    }
    cin >> Q;
    fill_n(ans, Q, -1);
    for(int i = 0; i < Q; i++){
        int L, R;
        cin >> L >> R;
        L--; R--;
        queries[R].emplace_back(L, i);
    }
    solve();
    for(int i = 0; i < N; i++) H[i] = -H[i];
    solve();
    for(int i = 0; i < Q; i++) cout << ans[i] << "\n";
}

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