Submission #262434

#	Time	Username	Problem	Language	Result	Execution time	Memory
262434		doowey	Two Antennas (JOI19_antennas)	C++14	100 / 100	1254 ms	93108 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 100;
const ll inf = (ll)1e16;
vector<int> add[N], rem[N];
int H[N], A[N], B[N];

struct Node{
    ll lazy;
    ll mxa;
    ll res;
};

Node T[N * 4];

void init(){
    for(int i = 0 ; i < N * 4; i ++ ){
        T[i] = {-inf, -inf, -inf};
    }
}

void push(int node, int cl, int cr){
    T[node].res = max(T[node].res, T[node].mxa + T[node].lazy);
    if(cl != cr){
        T[node * 2].lazy = max(T[node * 2].lazy, T[node].lazy);
        T[node * 2 + 1].lazy = max(T[node * 2 + 1].lazy, T[node].lazy);
    }
    T[node].lazy = -inf;
}

void setv(int node, int cl, int cr, int pos, ll vl){
    push(node, cl, cr);
    if(cl == cr){
        T[node].mxa = vl;
        T[node].res = max(T[node].res, T[node].mxa + T[node].lazy);
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= pos){
        setv(node * 2, cl, mid, pos, vl);
    }
    else{
        setv(node * 2 + 1, mid + 1, cr, pos, vl);
    }
    T[node].res = max({T[node].res, T[node * 2].res, T[node * 2 + 1].res});
    T[node].mxa = max(T[node * 2].mxa, T[node * 2 + 1].mxa);
}

ll get(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return -inf;
    if(cl >= tl && cr <= tr)
        return T[node].res;
    int mid = (cl + cr) / 2;
    return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}

void upd(int node, int cl, int cr, int tl, int tr, ll vl){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = vl;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, vl);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, vl);
    T[node].res = max({T[node].res, T[node * 2].res, T[node * 2 + 1].res});
}

int n;
int L[N], R[N];
vector<int> iq[N];
ll answ[N];
void solve(){
    init();
    int ni, nj;
    for(int i = 1; i <= n; i ++ ){
        for(auto x  : add[i]){
            setv(1, 1, n, x, -H[x]);
        }
        ni = max(1, i - B[i]);
        nj = max(0, i - A[i]);
        upd(1, 1, n, ni, nj, H[i]);
        for(auto x : iq[i]){
            answ[x] = max(answ[x], get(1, 1, n, L[x], R[x]));
        }
        for(auto x : rem[i]){
            setv(1, 1, n, x, -inf);
        }
    }

}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> H[i] >> A[i] >> B[i];
        add[i + A[i]].push_back(i);
        rem[i + B[i]].push_back(i);
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i ++ ){
        cin >> L[i] >> R[i];
        iq[R[i]].push_back(i);
        answ[i] = -inf;
    }
    solve();
    for(int i = 1; i <= n; i ++ )
        H[i] = -H[i];
    solve();
    for(int i = 1; i <= q; i ++ ){
        if(answ[i] < 0)
            answ[i] = -1;
        cout << answ[i] << "\n";
    }
    return 0;
}

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