Submission #1058309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058309		hotboy2703	Two Antennas (JOI19_antennas)	C++17	100 / 100	1663 ms	164120 KiB

antennas

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
const ll INF = 1e18;
pll lazy[MAXN*4];
ll tree[MAXN*4];
set <pll> s[MAXN*4];
const pll worst = MP(INF,-INF);
bool ok[MAXN];
ll n;
ll h[MAXN],a[MAXN],b[MAXN];
void build(ll id,ll l,ll r){
    if (l!=r){
        ll mid = (l + r) >> 1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
    tree[id] = -INF;
    lazy[id] = worst;
}
void push(ll id,pll v){
    lazy[id].fi = min(lazy[id].fi,v.fi);
    lazy[id].se = max(lazy[id].se,v.se);
    if (sz(s[id]))tree[id] = max({tree[id],(*s[id].rbegin()).fi - lazy[id].fi,-(*s[id].begin()).fi + lazy[id].se});
}
void update2(ll id,ll l,ll r,ll l1,ll r1,ll v){
    if (l > r1 || l1 > r || l1 > r1)return;
    if (l1 <= l && r <= r1){
        push(id,MP(v,v));
        // cout<<id<<' '<<l<<' '<<r<<' '<<tree[id]<<'\n';
        // for (auto x:s[id])cout<<x.fi<<' ';
        // cout<<'\n';
        return;
    }
    push(id<<1,lazy[id]);
    push(id<<1|1,lazy[id]);
    lazy[id] = worst;
    ll mid = (l + r) >> 1;
    update2(id<<1,l,mid,l1,r1,v);
    update2(id<<1|1,mid+1,r,l1,r1,v);
    tree[id] = -INF;
    if (sz(s[id]))tree[id] = max((*s[id].rbegin()).fi - lazy[id].fi,-(*s[id].begin()).fi + lazy[id].se);
    tree[id] = max({tree[id],tree[id<<1],tree[id<<1|1]});
}
void update(ll id,ll l,ll r,pll sus,ll i){
    sus.fi = min(sus.fi,lazy[id].fi);
    sus.se = max(sus.se,lazy[id].se);
    if (l > i || r < i)return;
    if (l == r){
        if (ok[i] == 0){
            ok[i] = 1;
            lazy[id] = worst;
            s[id] = {MP(h[i],i)};
            tree[id] = -INF;
        }
        else{
            ok[i] = 0;
            tree[id] = max(h[i]-sus.fi,sus.se-h[i]);
            lazy[id] = worst;
            s[id] = {};
        }
        return;
    }
    push(id<<1,lazy[id]);
    push(id<<1|1,lazy[id]);
    lazy[id] = worst;
    ll mid = (l + r) >> 1;
    if (ok[i]==0){
        s[id].insert(MP(h[i],i));
    }
    else{
        s[id].erase(MP(h[i],i));
    }
    update(id<<1,l,mid,sus,i);
    update(id<<1|1,mid+1,r,sus,i);
    // cout<<"UPD "<<id<<' '<<l<<' '<<r<<' '<<i<<endl;
    
    tree[id] = -INF;
    if (sz(s[id]))tree[id] = max((*s[id].rbegin()).fi - lazy[id].fi,-(*s[id].begin()).fi + lazy[id].se);
    tree[id] = max({tree[id],tree[id<<1],tree[id<<1|1]});
}
ll get(ll id,ll l,ll r,ll l1,ll r1){
    if (l > r1 || l1 > r || l1 > r1)return -INF;
    if (l1 <= l && r <= r1)return tree[id];
    ll mid = (l + r) >> 1;
    push(id<<1,lazy[id]);
    push(id<<1|1,lazy[id]);
    lazy[id] = worst;
    return max(get(id<<1,l,mid,l1,r1),get(id<<1|1,mid+1,r,l1,r1));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    for (ll i = 1;i <= n;i ++)cin>>h[i]>>a[i]>>b[i];
    ll q;
    cin>>q;
    vector <pair <pll,ll> > query(q);
    for (ll j = 0;j < q;j ++)cin>>query[j].fi.fi>>query[j].fi.se,query[j].se = j;
    sort(query.begin(),query.end(),[](pair <pll,ll> x,pair <pll,ll> y){return x.fi.se < y.fi.se;});
    build(1,1,n);
    vector <pll> event;
    for (ll i = 1;i <= n;i ++)event.push_back(MP(i+a[i],i)),event.push_back(MP(i+b[i]+1,i));
    sort(event.begin(),event.end());
    vector <ll> ans(q);
    for (ll i = 1,ptre = 0,ptrq=0;i <= n;i ++){
        while (ptre < sz(event) && event[ptre].fi == i){
            update(1,1,n,worst,event[ptre].se);
            ptre++;
        }
        // for (ll j = 1;j <= n; j++)cout<<ok[j]<<' ';
        // cout<<'\n';
        update2(1,1,n,i-b[i],i-a[i],h[i]);
        // cout<<"WAT "<<tree[1]<<'\n';
        while (ptrq < sz(query) && query[ptrq].fi.se == i){
            ans[query[ptrq].se] = get(1,1,n,query[ptrq].fi.fi,query[ptrq].fi.se);
            ptrq++;
        }
    }
    for (auto &x:ans)cout<<(x<0?-1:x)<<'\n';
}

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