제출 #1298818

#제출 시각아이디문제언어결과실행 시간메모리
1298818khoavn2008Two Antennas (JOI19_antennas)C++17
0 / 100
298 ms30736 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
const ll MOD = 1e9 + 7, N = 2e5 + 36, LOG = 18;
const int INF = 1e9 + 36;
struct SegmentTree{
    int n;
    vector<int> maxH,minH,maxC,minlz,maxlz;
    SegmentTree(int n = 0):n(n){
        maxH.assign(n * 4 + 1, -INF);
        minH.assign(n * 4 + 1, INF);
        maxC.assign(n * 4 + 1, -INF);
        minlz.assign(n * 4 + 1, -1);
        maxlz.assign(n * 4 + 1, -1);
    }
    void apply(int c,int val){
        maxC[c] = max(maxC[c], maxH[c] - val);
        maxC[c] = max(maxC[c], val - minH[c]);
        maxH[c] = max(maxH[c], val);
        minH[c] = min(minH[c], val);
        if(maxlz[c] == -1)maxlz[c] = val;
        if(minlz[c] == -1)minlz[c] = val;
        maxlz[c] = max(maxlz[c], val);
        minlz[c] = min(minlz[c], val);
    }
    void pushDown(int c,int l,int r){
        if(maxlz[c] == -1)return;
        apply(l, maxlz[c]);
        apply(r, maxlz[c]);
        apply(l, minlz[c]);
        apply(r, minlz[c]);
        maxlz[c] = -1;
        minlz[c] = -1;
    }
    void merge(int c,int l,int r){
        maxC[c] = max(maxC[l], maxC[r]);
        maxH[c] = max(maxH[l], maxH[r]);
        minH[c] = min(minH[l], minH[r]);
    }
    void setValue(int p,int val,int id,int l,int r){
        //val == -1 -> del
        if(r < p || p < l)return;
        if(l == r){
            if(val == -1){
                maxH[id] = -INF;
                minH[id] = INF;
            }else maxH[id] = minH[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(id, id * 2, id * 2 + 1);
        setValue(p, val, id * 2, l, mid);
        setValue(p, val, id * 2 + 1, mid + 1, r);
        merge(id, id * 2, id * 2 + 1);
    }
    void update(int u,int v,int val,int id,int l,int r){
        if(r < u || v < l)return;
        if(u <= l && r <= v){
            apply(id, val);
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(id, id * 2, id * 2 + 1);
        update(u, v, val, id * 2, l, mid);
        update(u, v, val, id * 2 + 1, mid + 1, r);
        merge(id, id * 2, id * 2 + 1);
    }
    int getMaxC(int u,int v,int id,int l,int r){
        if(v < l || r < u)return -INF;
        if(u <= l && r <= v)return maxC[id];
        int mid = (l + r) >> 1;
        pushDown(id, id * 2, id * 2 + 1);
        return max(getMaxC(u, v, id * 2, l, mid), getMaxC(u, v, id * 2 + 1, mid + 1, r));
    }

    void printTree(int id,int l,int r){
        cout<<'['<<l<<' '<<r<<"] : "<<maxH[id]<<' '<<minH[id]<<' '<<maxC[id]<<endl;
        if(l == r)return;
        int mid = (l + r) >> 1;
        pushDown(id, id * 2, id * 2 + 1);
        printTree(id * 2, l, mid);
        printTree(id * 2 + 1, mid + 1, r);
    }

    void setValue(int p,int val){setValue(p, val, 1, 1, n);}
    void update(int u,int v,int val){update(u, v, val, 1, 1, n);}
    int getMaxC(int u,int v){return getMaxC(u, v, 1, 1, n);}
}S;
int n,q,h[N],a[N],b[N],ans[N];
pair<int,int> Q[N];
vector<int> event[N];
vector<pair<int,int>> ask[N];
void addEvent(int pos,int id,bool open){
    if(pos > n)return;
    if(open)event[pos].pb(id);
    else event[pos].pb(-id);
}
int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    S = SegmentTree(n);
    FOR(i,1,n)cin>>h[i]>>a[i]>>b[i];
    cin>>q;
    FOR(i,1,q){
        cin>>Q[i].fi>>Q[i].se;
        ask[Q[i].se].pb({Q[i].fi, i});
        ans[i] = -1;
    }
    FOR(i,1,n){
        REP(j, size(event[i])){
            int v = event[i][j];
            if(v > 0)S.setValue(v, h[v]);
            else S.setValue(-v, -1);
        }
        S.update(i - b[i], i - a[i], h[i]);
        REP(j, size(ask[i])){
            int l = ask[i][j].fi, idx = ask[i][j].se;
            ans[idx] = max(ans[idx], S.getMaxC(l, i));
        }
        addEvent(i + a[i], i, 1);
        addEvent(i + b[i] + 1, i, 0);
    }
    FOR(i,1,q)cout<<ans[i]<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...