제출 #1165072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165072		Math4Life2020	Two Antennas (JOI19_antennas)	C++20	100 / 100	421 ms	57072 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 262144; const ll E = 18; const ll INF = 1e18;
ll ans[Nm];
ll H[Nm]; ll A[Nm]; ll B[Nm];
vector<pii> qryv[Nm]; //qryv[r] -> {l,i}
vector<ll> ton[Nm]; //vector of i: turn on
vector<ll> toff[Nm]; //vector of i: turn off

bool islz[2*Nm]; //default 0: is there a lazy tag?
ll maxon[2*Nm]; //maximum on
ll minon[2*Nm]; //miniumum on
ll maxap[2*Nm]; //maximum applied
ll minap[2*Nm]; //minimum applied
ll stv[2*Nm]; //segtree value

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

void pdn(ll p) {
    if (p==0 || !islz[p]) {
        return;
    }
    islz[p]=0;
    stv[p]=max(stv[p],maxon[p]-minap[p]);
    stv[p]=max(stv[p],maxap[p]-minon[p]);
    //cout << "pdn(p="<<p<<"): stv="<<stv[p]<<"\n";
    if (p<Nm) {
        maxap[2*p]=max(maxap[p],maxap[2*p]);
        maxap[2*p+1]=max(maxap[p],maxap[2*p+1]);
        minap[2*p]=min(minap[p],minap[2*p]);
        minap[2*p+1]=min(minap[p],minap[2*p+1]);
        maxap[p]=-INF;
        minap[p]=INF;
        islz[2*p]=1;
        islz[2*p+1]=1;
    }
}

void lft(ll p) {
    if (p==0 || islz[p] || p>=Nm) {
        return;
    }
    maxon[p]=max(maxon[2*p+1],maxon[2*p]);
    minon[p]=min(minon[2*p+1],minon[2*p]);
    stv[p]=max(stv[p],stv[2*p]);
    stv[p]=max(stv[p],stv[2*p+1]);
}

void pdnP(ll p) {
    for (ll e=E;e>=0;e--) {
        pdn(p>>e);
    }
}

void lftP(ll p) {
    for (ll e=1;e<=E;e++) {
        lft(p>>e);
    }
}

void gon(ll v) {
    ll p = v+Nm;
    pdnP(p);
    maxon[p]=H[v];
    minon[p]=H[v];
    maxap[p]=-INF;
    minap[p]=INF;
    lftP(p);
}

void goff(ll v) {
    ll p = v+Nm;
    pdnP(p);
    maxon[p]=-INF;
    minon[p]=INF;
    maxap[p]=-INF;
    minap[p]=INF;
    lftP(p);
}

void appl(ll l, ll r, ll h) {
    if (l>r) {
        return;
    }
    //cout << "applB: "<<l<<","<<r<<","<<h<<"\n";
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        ll p = (l>>vl)+(1<<(E-vl));
        pdnP(p);
        maxap[p]=max(maxap[p],h);
        minap[p]=min(minap[p],h);
        stv[p]=max(stv[p],maxap[p]-minon[p]);
        stv[p]=max(stv[p],maxon[p]-minap[p]);
        islz[p]=1;
        lftP(p);
        appl(l+(1<<vl),r,h);
    } else {
        ll p = (r>>vr)+(1<<(E-vr));
        pdnP(p);
        maxap[p]=max(maxap[p],h);
        minap[p]=min(minap[p],h);
        stv[p]=max(stv[p],maxap[p]-minon[p]);
        stv[p]=max(stv[p],maxon[p]-minap[p]);
        islz[p]=1;
        lftP(p);
        appl(l,r-(1<<vr),h);
    }
}

ll qry(ll l, ll r) {
    if (l>r) {
        return -INF;
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        ll p = (l>>vl)+(1<<(E-vl));
        pdnP(p);
        //cout << "p="<<p<<", stv="<<stv[p]<<"\n";
        return max(qry(l+(1<<vl),r),stv[p]);
    } else {
        ll p = (r>>vr)+(1<<(E-vr));
        pdnP(p);
        //cout << "p="<<p<<", stv="<<stv[p]<<"\n";
        return max(qry(l,r-(1<<vr)),stv[p]);
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    for (ll p=0;p<(2*Nm);p++) {
        maxon[p]=-INF;
        minon[p]=INF;
        maxap[p]=-INF;
        minap[p]=INF;
        stv[p]=-INF;
    }
    ll N; cin >> N;
    for (ll i=0;i<N;i++) {
        cin >> H[i] >> A[i] >> B[i];
        if ((i+A[i])<N) {
            ton[i+A[i]].push_back(i);
            toff[min(i+B[i],N-1)].push_back(i);
        }
    }
    ll Q; cin >> Q;
    for (ll q=0;q<Q;q++) {
        ll l,r; cin >> l >> r;
        l--; r--;
        qryv[r].push_back({l,q});
    }
    for (ll i=0;i<N;i++) {
        for (ll v: ton[i]) {
            //cout << "gon: "<<v<<"\n";
            gon(v); //get on
        }
        if ((i-A[i])>=0) {
            //cout << "appl: "<<max(0LL,i-B[i])<<","<<(i-A[i])<<","<<H[i]<<"\n";
            appl(max(0LL,i-B[i]),i-A[i],H[i]);
        }
        for (pii p0: qryv[i]) {
            //cout << "qry to "<<p0.second<<": "<<p0.first<<","<<i<<"\n";;
            ans[p0.second]=qry(p0.first,i);
        }
        for (ll v: toff[i]) {
            //cout <<"goff: "<<v<<"\n";
            goff(v);
        }
    }
    for (ll q=0;q<Q;q++) {
        if (ans[q]>=0) {
            cout << ans[q] <<"\n";
        } else {
            cout << "-1\n";
        }
    }
}

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