Submission #1110120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110120		imarn	Two Antennas (JOI19_antennas)	C++14	100 / 100	489 ms	77520 KiB

antennas

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e5+5;
ll h[mxn];
int a[mxn],b[mxn];
vector<pii>qr[mxn];
vector<pii>g[2*mxn];
struct lazy{
    ll t[4*mxn]{0},lz[4*mxn]{0},c[4*mxn]{0};
    void build(int n,ll amt){
        for(int i=1;i<=4*n;i++)t[i]=-1,lz[i]=2e16,c[i]=amt;
    }
    void upd(int i,int l,int r,int idx,ll v){
        if(r<idx||l>idx)return;
        if(l==r)return void(c[i]=v);
        int m=(l+r)>>1;
        upd(2*i,l,m,idx,v);upd(2*i+1,m+1,r,idx,v);
        c[i]=max(c[2*i],c[2*i+1]);
    }
    void push(int i,int l,int r){
        t[i]=max(t[i],c[i]-lz[i]);
        if(l<r)lz[2*i]=min(lz[2*i],lz[i]),lz[2*i+1]=min(lz[2*i+1],lz[i]);
        lz[i]=2e16;
    }
    void update(int i,int l,int r,int tl,int tr,ll v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]=min(lz[i],v);
            push(i,l,r);return;
        }int m=(l+r)>>1;
        update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
        t[i]=max(t[2*i],t[2*i+1]);
    }
    ll qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return -1;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return max(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}sg[2];ll ans[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
        g[i+a[i]].pb({i,h[i]});
        g[i+b[i]+1].pb({i,-h[i]});
    }int q;cin>>q;
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        qr[r].pb({l,i});
    }
    sg[0].build(n,-2e9);sg[1].build(n,-2e9);
    for(int i=1;i<=n;i++){
        for(auto [id,h]:g[i]){
            if(h>0){
                sg[0].qr(1,1,n,id,id);
                sg[0].upd(1,1,n,id,h);
                sg[1].qr(1,1,n,id,id);
                sg[1].upd(1,1,n,id,-h);
            }
            else {
                sg[0].qr(1,1,n,id,id);
                sg[0].upd(1,1,n,id,-2e9);
                sg[1].qr(1,1,n,id,id);
                sg[1].upd(1,1,n,id,-2e9);
            }
        }
        if(i-a[i]>=1){
            sg[0].update(1,1,n,max(1,i-b[i]),i-a[i],h[i]);
            sg[1].update(1,1,n,max(1,i-b[i]),i-a[i],-h[i]);
        }
        for(auto [l,id]:qr[i]){
            ans[id]=max(sg[0].qr(1,1,n,l,i),sg[1].qr(1,1,n,l,i));
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for(auto [id,h]:g[i]){
      |                  ^
antennas.cpp:87:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for(auto [l,id]:qr[i]){
      |                  ^

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