Submission #489999

#	Time	Username	Problem	Language	Result	Execution time	Memory
489999		balbit	Two Antennas (JOI19_antennas)	C++14	100 / 100	996 ms	59356 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;


ll H[maxn], A[maxn], B[maxn];
int n;
vector<pair<int, int> > ev[maxn]; // who, build/not build (1/0)

ll superinf = -inf-inf-1;
ll a[maxn*4], c[maxn*4], tg[maxn*4], d[maxn*4]; // d = max(c-a)
bool istg[maxn*4];

void push(int o, int l, int r) {
    if (tg[o] != superinf) {
        MX(c[o], tg[o]);
        MX(d[o], tg[o] - a[o]);
        if (l!=r) {
            MX(tg[o*2], tg[o]);
            MX(tg[o*2+1], tg[o]);
        }
        tg[o] = superinf;
    }
}

inline void pull(int o) {
    a[o] = min(a[o*2], a[o*2+1]);
    c[o] = max(c[o*2], c[o*2+1]);
    d[o] = max(d[o], max(d[o*2], d[o*2+1]));
}

void MOset(int p, bool moa, ll v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l > p || r < p) return;
    if (l == r) {
        if (moa) a[o] = v;
        else c[o] = v;
        MX(d[o], c[o]-a[o]);
        return;
    }
    int mid = (l+r)/2;
    MOset(p, moa, v, o*2,l,mid);
    MOset(p, moa, v, o*2+1,mid+1,r);
    pull(o);
}

void MOrng(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        MX(tg[o], v);
        push(o,l,r);
        return;
    }
    int mid = (l+r)/2;
    MOrng(L,R,v,o*2,l,mid);
    MOrng(L,R,v,o*2+1,mid+1,r);
    pull(o);
}

ll QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
    if (l > R || r < L) return -inf;
    push(o,l,r);
    if (l >= L && r <= R) return d[o];
    int mid = (l+r)/2;
    return max(QU(L,R,o*2,l,mid),
               QU(L,R,o*2+1,mid+1,r)
               );
}

vector<pii> ask[maxn];
ll ans[maxn];

void go(){
    REP(i,maxn*4){
        a[i] = inf;
        c[i] = -inf;
        d[i] = -inf;
        tg[i] = superinf;
    }
    REP(r,n) {
        for (pii p : ev[r]) {
            int who = p.f;
            bool build = p.s;
            if (build){
                MOset(who, 0, -inf);
                MOset(who, 1, H[who]);
            }else{
                MOset(who, 1, inf);
            }
        }
        // do me!
        int lp = max(0ll, r-B[r]), rp = max(-1ll, r-A[r]);
        MOrng(lp, rp, H[r]);

        for (pii p : ask[r]) {
            ans[p.s] = max(ans[p.s], QU(p.f, r));
//            if (QU(p.f, r) == 9) {
//                bug(r);
//            }
        }
    }
}

signed main(){
    IOS();
    memset(ans, -1, sizeof ans);
    cin>>n;
    REP(i,n) {
        cin>>H[i]>>A[i]>>B[i];
    }
    int q; cin>>q;
    REP(i,q) {
        int l,r; cin>>l>>r; --l; --r;
        ask[r].pb({l,i});
    }
    REP(i,n) {
        if (i+A[i] < n) ev[i+A[i]].pb({i,1});
        if (i+B[i]+1 < n) ev[i+B[i]+1].pb({i,0});
    }

    go();
    REP(i,n) H[i] = -H[i];
    go();
    REP(i,q) {
        cout<<ans[i]<<endl;
    }

}

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