Submission #1297426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297426		tdkhai	Two Antennas (JOI19_antennas)	C++20	100 / 100	289 ms	41912 KiB

antennas

#include<bits/stdc++.h>
#define ii pair<int,int>
//#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define tdk "tdk"
#define db double

using namespace std;

const ll INF = 1e18;
const int inf=1e9;

const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

const int N=2e5+5;
int a[N],b[N],h[N],ans[N],n,q;
vector<int> in[N],out[N];
vector<ii> query[N];
struct smt
{
    struct node
    {
        int maxh,minh,lazymax,lazymin,res;
    };
    node mg(node a,node b)
    {
        node ret;
        ret.maxh=max(a.maxh,b.maxh);
        ret.minh=min(a.minh,b.minh);
        ret.res=max(a.res,b.res);
        ret.lazymin=inf;
        ret.lazymax=-inf;
        return ret;
    }
    node st[N<<2+3];
    void init()
    {
        for(int i=0;i<=N<<2;i++)
        {
            st[i]={-inf,inf,-inf-1,inf,-1};
        }
    }
    void push(int id)
    {
        int nxt=id*2,&mx=st[id].lazymax,&mn=st[id].lazymin;
        st[nxt].lazymax=max(st[nxt].lazymax,mx);
        st[nxt+1].lazymax=max(st[nxt+1].lazymax,mx);
//        st[nxt].maxh=max(st[nxt].maxh,mx);
//        st[nxt+1].maxh=max(st[nxt+1].maxh,mx);
//        st[nxt].minh=min(st[nxt].minh,mn);
//        st[nxt+1].minh=min(st[nxt+1].minh,mn);
        st[nxt].lazymin=min(st[nxt].lazymin,mn);
        st[nxt+1].lazymin=min(st[nxt+1].lazymin,mn);
        st[nxt].res=max({st[nxt].res,st[nxt].maxh-mn,mx-st[nxt].minh});
        st[nxt+1].res=max({st[nxt+1].res,st[nxt+1].maxh-mn,mx-st[nxt+1].minh});
        mx=-inf,mn=inf;
    }
    void update(int id,int l,int r,int u,int val)
    {
        if(l==r)
        {
            if(val==-1)
            {
                st[id].maxh=-inf;
                st[id].minh=inf;
            }
            else
            {
                st[id].maxh=val;
                st[id].minh=val;
            }
        }
        else
        {
            int mid=l+r>>1;
            push(id);
            if(u<=mid) update(id*2,l,mid,u,val);
            else update(id*2+1,mid+1,r,u,val);
            st[id]=mg(st[id*2],st[id*2+1]);
        }
    }
    void updaterng(int id,int l,int r,int u,int v,int val)
    {
        if(l>v or r<u) return;
        if(l>=u and r<=v)
        {
            st[id].res=max({st[id].res,val-st[id].minh,st[id].maxh-val});
//            st[id].minh=min(st[id].minh,val);
//            st[id].maxh=max(st[id].maxh,val);
            st[id].lazymax=max(st[id].lazymax,val);
            st[id].lazymin=min(st[id].lazymin,val);
        }
        else
        {
            push(id);
            int mid=l+r>>1;
            updaterng(id*2,l,mid,u,v,val);
            updaterng(id*2+1,mid+1,r,u,v,val);
            st[id]=mg(st[id*2],st[id*2+1]);
        }
    }
    int get(int id,int l,int r,int u,int v)
    {
        if(l>v or r<u) return -1;
        if(l>=u and r<=v) return st[id].res;
        int mid=l+r>>1;
        push(id);
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}T;
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> h[i] >> a[i] >> b[i];
    }
    T.init();
    for(int i=1;i<=n;i++)
    {
        if(i+a[i]<=n)
        {
            in[i+a[i]].pb(i);
        }
        if(i+b[i]<n)
        {
            out[i+b[i]+1].pb(i);
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin >> l >> r;
        query[r].pb({l,i});
    }
    for(int i=1;i<=n;i++)
    {
//        cout << "in" << " ";
        for(int j:in[i])
        {
//            cout << j << ' ';
            T.update(1,1,n,j,h[j]);
        }
//        cout << '\n'  << "out ";
        for(int j:out[i])
        {
//            cout << j <<  ' ';
            T.update(1,1,n,j,-1);
        }
//        cout << '\n';
        if(i-a[i]>=1)
        {
            T.updaterng(1,1,n,max(1,i-b[i]),i-a[i],h[i]);
        }
        for(ii j:query[i])
        {
            int l=j.fi,id=j.se;
            ans[id]=T.get(1,1,n,l,i);
        }
    }
    for(int i=1;i<=q;i++)
    {
        cout << ans[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
//    cin >> t;
    while(t--)
    {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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