제출 #1101843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101843		vjudge1	Two Antennas (JOI19_antennas)	C++17	100 / 100	668 ms	94788 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define all(x) x.begin(),x.end()
#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

const ll maxn=4e5+69;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=1e9+7;

int n,mn[maxn*4],mx[maxn*4],st[maxn*4],a[maxn],b[maxn],h[maxn],l[maxn],r[maxn],ans[maxn];
vector<int> in[maxn],out[maxn],qr[maxn];
void push(int id)
{

    mn[id*2]=min(mn[id],mn[id*2]);
//    st[id*2]=max(st[id*2],mx[id*2]-mn[id*2]);
    mn[id*2+1]=min(mn[id],mn[id*2+1]);
//    st[id*2+1]=max(st[id*2+1],mx[id*2+1]-mn[id*2+1]);
    mn[id]=inf;
}
void Update(int u,int v,int id=1,int l=1,int r=n)
{
    st[id]=max(st[id],mx[id]-mn[id]);
    push(id);
    if (l==r)
    {
        mx[id]=v;
        return;
    }
    int mid=l+r>>1;
    if (u<=mid) Update(u,v,id*2,l,mid);
    else Update(u,v,id*2+1,mid+1,r);
    mx[id]=max(mx[id*2],mx[id*2+1]);
}
void Update_real(int u,int v,int val,int id=1,int l=1,int r=n)
{
    st[id]=max(st[id],mx[id]-mn[id]);
    push(id);
    if (u>r || v<l) return;
    if (u<= l && r<=v)
    {
        mn[id]=val;
        st[id]=max(st[id],mx[id]-mn[id]);
        push(id);
        return;
    }
    int mid=l+r>>1;
    Update_real(u,v,val,id*2,l,mid);
    Update_real(u,v,val,id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
}
int Get(int u,int v,int id=1,int l=1,int r=n)
{
    st[id]=max(st[id],mx[id]-mn[id]);
    push(id);
    if (u>r || v<l) return -inf;
    if (u<=l && r<=v) return st[id];
    int mid=l+r>>1;
    return max(Get(u,v,id*2,l,mid),Get(u,v,id*2+1,mid+1,r));
}

void solve()
{
    for1(i,1,n*4) mx[i]=st[i]=-1,mn[i]=inf;
    for1(i,1,n)
    {
        in[i+a[i]].pb(i);
        out[i+b[i]].pb(i);
        for(int j:in[i])
        {
            Update(j,h[j]);
//            cerr<<"cdc "<<i<<' '<< j<<' '<<h[j]<<'\n';
        }
//        if (i==3) cerr<< i-b[i]<<' '<<i-a[i]<<'\n';
        Update_real(i-b[i],i-a[i],h[i]);
        for(int j:qr[i]) ans[j]=max(ans[j],Get(l[j],r[j]));
        for(int j:out[i]) Update(j,-1);
        in[i].clear();
        out[i].clear();
    }
}

void sol()
{
    cin >> n;
    for1(i,1,n)
    {
        cin >> h[i]>> a[i]>> b[i];
    }
    int q; cin >> q;
    for1(i,1,q)
    {
        cin >> l[i]>> r[i];
        qr[r[i]].pb(i);
        ans[i]=-1;
    }
    solve();
    for1(i,1,n) h[i]=1e9-h[i];
    solve();
    for1(i,1,q) cout << ans[i]<<'\n';

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("990G.inp","r",stdin);
//    freopen("990G.out","w",stdout);

    int t=1;//cin >> t;
    for1(i,1,t) {
//        cout << "Case #"<<i<<": ";
        sol();
    }
}

/*
3
10 2 4
2 1 1
1 1 3
1
2 3



*/

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid=l+r>>1;
      |             ~^~
antennas.cpp: In function 'void Update_real(long long int, long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid=l+r>>1;
      |             ~^~
antennas.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid=l+r>>1;
      |             ~^~

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