제출 #1288310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288310		simona1230	Two Antennas (JOI19_antennas)	C++20	13 / 100	1614 ms	589824 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

struct ant
{
    int h,a,b;
    ant(){}
    ant(int _h,int _a,int _b)
    {
        h=_h;
        a=_a;
        b=_b;
    }
};

int n;
ant t[200001];
int q;
pair<int,int> p[200001];

void read()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        t[i]={x,y,z};
    }

    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>p[i].first>>p[i].second;
    }
}

vector<int> v[200001],d[200001];

void prec()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+t[i].a;j<=i+t[i].b;j++)
        {
            if(j-t[j].b<=i&&i<=j-t[j].a)
            {
                v[i].push_back(j);
                if(d[i].size()==0)d[i].push_back(abs(t[i].h-t[j].h));
                else d[i].push_back(max(d[i][d[i].size()-1],abs(t[i].h-t[j].h)));
            }
        }
    }
    //cout<<"done"<<endl;
}

void solve()
{
    for(int i=1;i<=q;i++)
    {
        int ans=-1;
        for(int j=p[i].first;j<=p[i].second;j++)
        {
            int id=-1;
            int l=0,r=v[j].size()-1;
            while(l<=r)
            {
                int m=(l+r)/2;
                if(v[j][m]<=p[i].second)
                {
                    id=m;
                    l=m+1;
                }
                else r=m-1;
            }

            if(id!=-1)
                ans=max(ans,d[j][id]);
        }
        cout<<ans<<endl;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	prec();
	solve();
	return 0;
}

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