Submission #444510

#	Time	Username	Problem	Language	Result	Execution time	Memory
444510		Dymo	Two Antennas (JOI19_antennas)	C++17	100 / 100	693 ms	32108 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
using namespace std;
#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937_64 rnd;

const ll maxn=2e5+10;
const ll mod =1e9+7 ;
const ll base=1e9+100;
/// you will be the best but now you just are trash
/// goal=1/7;

struct tk
{
    ll mx_all,mnc,mxc;
    ll la_mn;
    ll la_mx;
};
// val posnw;
// mx = mxnw;
tk st[4*maxn];
tk mer(tk a, tk b)
{
    tk c;
    if (a.mx_all==-base)
        return b;
    if (b.mx_all==-base)
        return a;
    c.mx_all=max(a.mx_all,b.mx_all);
    c.mnc=min(a.mnc,b.mnc);
    c.mxc=max(a.mxc,b.mxc);
    c.la_mn=base;
    c.la_mx=-base;
    return c;
}
void build(ll id,ll left,ll right)
{
    if (left==right)
    {
        st[id].mnc=base;
        st[id].mxc=-base;
        st[id].mx_all=-1;
        st[id].la_mn=base;
        st[id].la_mx=-base;
        return ;
    }
    ll mid=(left+right)/2;
    build(id*2,left,mid);
    build(id*2+1,mid+1,right);
    st[id]=mer(st[id*2],st[id*2+1]);
}
void dosth(ll id,ll left,ll right)
{
    if (left==right)
        return ;
    st[id*2].mx_all=max(st[id*2].mx_all,max(st[id].la_mx-st[id*2].mnc,st[id*2].mxc-st[id].la_mn));
    st[id*2+1].mx_all=max(st[id*2+1].mx_all,max(st[id].la_mx-st[id*2+1].mnc,st[id*2+1].mxc-st[id].la_mn));

    st[id*2].la_mn=min(st[id*2].la_mn,st[id].la_mn);
    st[id*2+1].la_mn=min(st[id*2+1].la_mn,st[id].la_mn);
    st[id*2].la_mx=max(st[id*2].la_mx,st[id].la_mx);
    st[id*2+1].la_mx=max(st[id*2+1].la_mx,st[id].la_mx);
    st[id].la_mn=base;
    st[id].la_mx=-base;
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
    if (x>right||x<left)
        return ;
    if (left==right)
    {
        if (diff==base)
        {
            st[id].mnc=base;
            st[id].mxc=-base;
            return ;
        }
        st[id].mnc=diff;
        st[id].mxc=diff;
        return ;
    }
    dosth(id,left,right);
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,diff);
    update(id*2+1,mid+1,right,x,diff);
    st[id]=mer(st[id*2],st[id*2+1]);
}
void update_val(ll id,ll left,ll right,ll x,ll y,ll val)
{
    if (x>right||y<left)
        return ;
    if (x<=left&&y>=right)
    {
        st[id].mx_all=max(st[id].mx_all,max(val-st[id].mnc,st[id].mxc-val));
        st[id].la_mn=min(st[id].la_mn,val);
        st[id].la_mx=max(st[id].la_mx,val);
        return ;
    }
    dosth(id,left,right);
    ll mid=(left+right)/2;
    update_val(id*2,left,mid,x,y,val);
    update_val(id*2+1,mid+1,right,x,y,val);
    st[id]=mer(st[id*2],st[id*2+1]);
}
ll get(ll id,ll left,ll right,ll x,ll y)
{
    if (x>right||y<left)
        return -1;
    if (x<=left&&y>=right)
        return st[id].mx_all;
    dosth(id,left,right);
    ll mid=(left+right)/2;
    return max(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
ll h[maxn];
ll a[maxn];
ll b[maxn];
ll ans[maxn];
vector<pll> p[maxn];
vector<pll> adj[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin>>n ;
    for (int i=1; i<=n; i++)
    {
        cin>>h[i]>>a[i]>>b[i];
    }
    ll q;
    cin>> q;
    for (int i=1; i<=q; i++)
    {
        ll l, r;
        cin>> l>> r;
        p[r].pb(make_pair(l,i));
    }
    build(1,1,n);
    for (int i=1; i<=n; i++)
    {
       if (i+a[i]<=n) adj[i+a[i]].pb(make_pair(i,h[i]));
       if (i+b[i]+1<=n) adj[i+b[i]+1].pb(make_pair(i,base));
       for (auto p:adj[i])
       {
           update(1,1,n,p.ff,p.ss);
       }
       ll l=max(1,i-b[i]);
       ll r=i-a[i];
       if (r>=l)
       {
           update_val(1,1,n,l,r,h[i]);
       }
       for (auto h:p[i])
       {
           ans[h.ss]=get(1,1,n,h.ff,i);
       }
    }
    for (int i=1;i<=q;i++)
    {
        cout <<ans[i]<<endl;
    }



}

Compilation message (stderr)

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

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