Submission #708381

#	Time	Username	Problem	Language	Result	Execution time	Memory
708381		victor_gao	Two Antennas (JOI19_antennas)	C++17	100 / 100	632 ms	84312 KiB

antennas

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct Node{
    int mx,mn,qmx,qmn,tag_mx,tag_mn,ans;
    // ans is qmx-mn,mx-qmn
    Node(int a=-1e18,int b=1e18,int c=-1e18,int d=1e18,int tag1=-1e18,int tag2=1e18,int e=-1e18):mx(a),mn(b),qmx(c),qmn(d),tag_mx(tag1),tag_mn(tag2),ans(e){}
    int get_ans(){ return ans=max({ans,qmx-mn,mx-qmn}); }
    void OUT(){
        cout<<mx<<" "<<mn<<" "<<qmx<<" "<<qmn<<" "<<ans<<'\n';
    }
};
struct segtree{
    Node seg[4*N];
    void add_tag(int i,int tag1,int tag2){
        if (seg[i].tag_mx<tag1){
            seg[i].tag_mx=tag1;
            seg[i].qmx=tag1;
            seg[i].get_ans();
        }
        if (seg[i].tag_mn>tag2){
            seg[i].tag_mn=tag2;
            seg[i].qmn=tag2;
            seg[i].get_ans();
        }
    }
    void push(int i){
        add_tag(2*i,seg[i].tag_mx,seg[i].tag_mn);
        add_tag(2*i+1,seg[i].tag_mx,seg[i].tag_mn);
        seg[i].tag_mn=1e18; seg[i].tag_mx=-1e18;
    }
    Node merge(Node a,Node b){
        Node ans=Node();
        ans.mx=max(a.mx,b.mx);
        ans.mn=min(a.mn,b.mn);
        ans.ans=max(a.ans,b.ans);
        return ans;
    }
    void change(int l,int r,int i,int pos,int val){ // 拔出現在放入的 r 並不在 pos 的區間內
        if (l==r){
            int tans=seg[i].ans;
            seg[i]=Node(); seg[i].ans=tans;
            if (val==0){
                seg[i].mx=-1e18;
                seg[i].mn=1e18;
            }
            else {
                seg[i].mn=val;
                seg[i].mx=val;
            }
            return;
        }
        int mid=(l+r)>>1; push(i);
        if (pos<=mid) change(l,mid,2*i,pos,val);
        else change(mid+1,r,2*i+1,pos,val);
        seg[i]=merge(seg[2*i],seg[2*i+1]);
    }
    void modify(int l,int r,int i,int ll,int rr,int val){
        if (ll>rr) return;
        if (ll<=l&&rr>=r){
            add_tag(i,val,val);
            return;
        }
        int mid=(l+r)>>1; push(i);
        if (rr<=mid) modify(l,mid,2*i,ll,rr,val);
        else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val);
        else {
            modify(l,mid,2*i,ll,rr,val);
            modify(mid+1,r,2*i+1,ll,rr,val);
        }
        seg[i]=merge(seg[2*i],seg[2*i+1]);
    }
    int query(int l,int r,int i,int ll,int rr){
        if (ll>rr) return -1e18;
        if (ll<=l&&rr>=r)
            return seg[i].ans;
        int mid=(l+r)>>1; push(i);
        if (rr<=mid) return query(l,mid,2*i,ll,rr);
        else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
        else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
    }
    void debug(int l,int r,int i){
        cout<<l<<" ~ "<<r<<" : ";
        seg[i].OUT();
        if (l==r){
            return;
        }
        int mid=(l+r)>>1; push(i);
        debug(l,mid,2*i); debug(mid+1,r,2*i+1);
    }
}seg;
int n,h[N],a[N],b[N],q,ans[N];
vector<int>in[N],out[N];
vector<pii>qry[N];
signed main(){
    fast
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
        in[min(i+a[i],n+1)].push_back(i);
        out[min(i+b[i],n+1)].push_back(i);
    }
    cin>>q;
    for (int i=1;i<=q;i++){
        int l,r; cin>>l>>r;
        qry[r].push_back({l,i});
    }
    for (int i=1;i<=n;i++){
        for (auto j:in[i]){
           // cout<<"In "<<j<<" "<<h[j]<<'\n';
            seg.change(1,n,1,j,h[j]);
        }
      //  cout<<"modify "<<max(1LL,i-b[i])<<" "<<max(0LL,i-a[i])<<" "<<h[i]<<'\n';
        seg.modify(1,n,1,max(1LL,i-b[i]),max(0LL,i-a[i]),h[i]);
     //   cout<<i<<" segtree : \n";
    //    seg.debug(1,n,1);
        for (auto [l,j]:qry[i]){
            ans[j]=seg.query(1,n,1,l,i);
    //        cout<<"query "<<l<<" "<<i<<" : "<<ans[j]<<'\n';
        }
        for (auto j:out[i]){
    //        cout<<"Out "<<j<<" "<<h[j]<<'\n';
            seg.change(1,n,1,j,0);
        }
    }
    for (int i=1;i<=q;i++)
        cout<<max(ans[i],-1LL)<<'\n';
}

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