Submission #1149392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149392		KhoaDuy	Two Antennas (JOI19_antennas)	C++17	0 / 100	122 ms	18992 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
pair<int,int> Tid={-1,-1};
int Uid=-1;
pair<int,int> TT(pair<int,int> &le,pair<int,int> &ri){
    pair<int,int> pa;
    pa.first=max(le.first,ri.first);
    pa.second=max(le.second,ri.second);
    return pa;
}
pair<int,int> UT(int &app,pair<int,int> &node){
    pair<int,int> pa;
    if(app==Uid){
        pa=node;
        return pa;
    }
    pa.first=node.first;
    pa.second=max(node.second,pa.first-app);
    return pa;
}
int UU(int &app,int &node){
    if(app==Uid){
        return node;
    }
    if(node==Uid){
        return app;
    }
    return min(app,node);
}
struct segtree{
    vector<pair<int,int>> seg;
    vector<int> d;
    int n,lg;
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(int siz){
        n=1;
        while(n<siz){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
        d.assign(n,Uid);
        for(int i=n-1;i>=1;i--){
            refresh(i);
        }
    }
    void apply(int v,int &f){
        seg[v]=UT(f,seg[v]);
        if(v<n){
            d[v]=UU(f,d[v]);
        }
    }
    void push(int v){
        apply(v<<1,d[v]);
        apply((v<<1)|1,d[v]);
        d[v]=Uid;
    }
    void update1(int l,int x){
        l+=n;
        for(int i=lg;i>=1;i--){
            push(l>>i);
        }
        seg[l].first=x;
        for(int i=1;i<=lg;i++){
            refresh(l>>i);
        }
    }
    void update2(int l,int r,int &f){
        l+=n,r+=n;
        if(l>=r){
            return;
        }
        for(int i=lg;i>=1;i--){
            if((l>>i<<i)!=l){
                push(l>>i);
            }
            if((r>>i<<i)!=r){
                push(r>>i);
            }
        }
        int l0=l,r0=r;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                apply(l,f);
                l++;
            }
            if(r&1){
                r--;
                apply(r,f);
            }
        }
        l=l0,r=r0;
        for(int i=1;i<=lg;i++){
            if((l>>i<<i)!=l){
                refresh(l>>i);
            }
            if((r>>i<<i)!=r){
                refresh(r>>i);
            }
        }
    }
    pair<int,int> query(int l,int r){
        l+=n,r+=n;
        if(l>=r){
            return Tid;
        }
        for(int i=lg;i>=1;i--){
            if((l>>i<<i)!=l){
                push(l>>i);
            }
            if((r>>i<<i)!=r){
                push(r>>i);
            }
        }
        pair<int,int> curr=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                curr=TT(curr,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                curr=TT(curr,seg[r]);
            }
        }
        return curr;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> h(n),a(n),b(n);
    for(int i=0;i<n;i++){
        cin >> h[i] >> a[i] >> b[i];
    }
    int q;
    cin >> q;
    int ans[q];
    memset(ans,-1,sizeof(ans));
    int l[q],r[q];
    for(int i=0;i<q;i++){
        cin >> l[i] >> r[i];
        l[i]--,r[i]--;
    }
    for(int phase=0;phase<2;phase++){
        if(phase==1){
            cout << ans[0] << endl;
            exit(0);
        }
        vector<vector<pair<int,int>>> que(n);
        vector<vector<pair<int,int>>> group(n);
        for(int i=0;i<q;i++){
            que[r[i]].push_back({l[i],i});
        }
        for(int i=0;i<n;i++){
            if(i+a[i]<n){
                group[i+a[i]].push_back({i,1});
                if(i+b[i]+1<n){
                    group[i+b[i]+1].push_back({i,-1});
                }
            }
        }
        segtree seg;
        seg.build(n);
        for(int r=0;r<n;r++){
            for(pair<int,int> &x:group[r]){
                if(x.second==1){
                    //cout << "UPD1 " << x.first << ' ' << h[x.first] << endl;
                    seg.update1(x.first,h[x.first]);
                }
                else{
                    //cout << "UPD1 " << x.first << ' ' << -1 << endl;
                    seg.update1(x.first,-1);
                }
            }
            if(r-a[r]>=0){
                //cout << "UPD2 " << max(r-b[r],0) << ' ' << r-a[r] << ' ' << h[r] << endl;
                seg.update2(max(r-b[r],0),r-a[r]+1,h[r]);
            }
            for(pair<int,int> &x:que[r]){
                //cout << "QUERY " << x.first << ' ' << r << endl;
                ans[x.second]=max(ans[x.second],seg.query(x.first,r+1).second);
            }
        }
        reverse(h.begin(),h.end());
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        for(int i=0;i<q;i++){
            l[i]=n-1-l[i],r[i]=n-1-r[i];
            swap(l[i],r[i]);
        }
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

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