Submission #1288694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288694		simona1230	Two Antennas (JOI19_antennas)	C++20	22 / 100	172 ms	19864 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];

int t[800001];

int query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[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 update(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        if(vl)t[i]=h[id];
        else t[i]=0;
        return;
    }

    int m=(l+r)/2;
    if(id<=m)update(i*2,l,m,id,vl);
    else update(i*2+1,m+1,r,id,vl);

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

int ans;
void sub3()
{
    for(int i=1;i<=n;i++)
        v1[i].clear(),
        v2[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);
        }
    }
    //cout<<"out"<<endl;

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

        //cout<<"? "<<i<<endl;
        ans=max(ans,query(1,1,n,max(1,i-b[i]),i-a[i])-h[i]);

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



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	sub3();
	reverse(a+1,a+n+1);
	reverse(b+1,b+n+1);
	reverse(h+1,h+n+1);
	sub3();
	cout<<ans<<endl;
	return 0;
}

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