Submission #1288947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288947		simona1230	Two Antennas (JOI19_antennas)	C++20	100 / 100	807 ms	41224 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
int n;
int a[200001];
int b[200001];
int h[200001];

int k;
pair<int,int> q[200001];

void read()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i]>>a[i]>>b[i];
    cin>>k;
    for(int i=1;i<=k;i++)
        cin>>q[i].first>>q[i].second;
}

vector<int> v1[200001],v2[200001],vq[200001];
int d[800001];
int c[800001];
int lz[800001];
// d[i]=max c[x]-h[i] -> max c[x]
// lz[i]=max h[i] that covers the interval

void push(int i,int l,int r)
{
    d[i]=max(d[i],c[i]-lz[i]);
    if(l!=r)
    {
        lz[i*2]=min(lz[i],lz[i*2]);
        lz[i*2+1]=min(lz[i],lz[i*2+1]);
    }
    lz[i]=1e9;
}

int query(int i,int l,int r,int ql,int qr)
{
    push(i,l,r);
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return d[i];
    int m=(l+r)/2;
    return max(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}

void upd1(int i,int l,int r,int id,int vl)
{
    push(i,l,r);
    if(id<l||r<id)return;

    if(l==r)
    {
        c[i]=vl;
        return;
    }

    int m=(l+r)/2;
    upd1(i*2,l,m,id,vl);
    upd1(i*2+1,m+1,r,id,vl);

    d[i]=max(d[i*2],d[i*2+1]);
    c[i]=max(c[i*2],c[i*2+1]);
}

void upd2(int i,int l,int r,int ql,int qr,int vl)
{
    push(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        lz[i]=vl;
        push(i,l,r);
        return;
    }

    int m=(l+r)/2;
    upd2(i*2,l,m,ql,min(m,qr),vl);
    upd2(i*2+1,m+1,r,max(m+1,ql),qr,vl);

    d[i]=max(d[i*2+1],d[i*2]);
}
int ans[200001];

int r;
void solve()
{
    //cout<<"in -----------------"<<endl;
    for(int i=1;i<=n;i++)
        v1[i].clear(),
        v2[i].clear(),
        vq[i].clear();

    for(int i=1;i<=n;i++)
    {
        if(i+a[i]<=n)
        {
            v1[i+a[i]].push_back(i);
            v2[min(n,i+b[i])].push_back(i);
        }
    }

    for(int i=1;i<=k;i++)
    {
        vq[q[i].second].push_back(i);
    }

    for(int i=1;i<=4*n;i++)
        d[i]=0,c[i]=0,lz[i]=1e9;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v1[i].size();j++)
        {
            upd1(1,1,n,v1[i][j],h[v1[i][j]]);
            //cout<<"+ "<<v1[i][j]<<" "<<h[v1[i][j]]<<endl;
        }

        upd2(1,1,n,max(1,i-b[i]),i-a[i],h[i]);
        //cout<<"> "<<max(1,i-b[i])<<" "<<i-a[i]<<" "<<h[i]<<endl;
        for(int j=0;j<vq[i].size();j++)
        {
            int id=vq[i][j];
            //cout<<i<<" "<<q[id].first<<" "<<q[id].second<<" "<<query(1,1,n,q[id].first,q[id].second)<<endl;
            ans[id]=max(ans[id],query(1,1,n,q[id].first,q[id].second));
        }

        for(int j=0;j<v2[i].size();j++)
        {
            upd1(1,1,n,v2[i][j],0);
            //cout<<"- "<<v2[i][j]<<endl;
        }
    }
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	reverse(a+1,a+n+1);
	reverse(b+1,b+n+1);
	reverse(h+1,h+n+1);
	for(int i=1;i<=k;i++)
        q[i].first=n-q[i].first+1,
        q[i].second=n-q[i].second+1,
        swap(q[i].first,q[i].second);
	solve();
	for(int i=1;i<=k;i++)
    {
        if(ans[i]==0)ans[i]=-1;
        cout<<ans[i]<<endl;
    }
	return 0;
}

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