제출 #1058255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058255		hotboy2703	Two Antennas (JOI19_antennas)	C++17	2 / 100	3088 ms	47900 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 = min(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 i = 0; i < q;i ++){
        ll l,r;
        cin>>l>>r;
        ll res = -INF;
        for (ll j = l;j <= r;j ++){
            for (ll k = j + 1;k <= r;k ++){
                if (abs(j-k) <= min(b[j],b[k]) && abs(j-k) >= max(a[j],a[k])){
                    res = max(res,abs(h[j]-h[k]));
                }
            }
        }
        if (res==-INF)res = -1;
        cout<<res<<'\n';
    }
    
}

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