Submission #1170079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170079		Szymon_Pilipczuk	Two Antennas (JOI19_antennas)	C++20	0 / 100	2 ms	1344 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
int h[2000];
int a[2000];
int b[2000];
int tr[2][2000][4000];
int n;
void add(int t1,int t,int p,int v)
{
    p+=n;
    tr[t1][t][p] = max(tr[t1][t][p],v);
    p/=2;
    while(p > 0)
    {
        tr[t1][t][p] = max(tr[t1][t][p*2],tr[t1][t][p*2+1]);
        p/=2;
    }
}
int check(int t1,int t,int l,int r)
{
    l+=n;
    r+=n;
    int ans = max(tr[t1][t][l],tr[t1][t][r]);
    while(l/2 != r/2)
    {
        if(l%2 == 0) ans = max(ans,tr[t1][t][l+1]);
        if(r%2 == 1) ans = max(ans,tr[t1][t][r-1]);
        l/=2;r/=2;
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i =0 ;i<n;i++)
    {
        cin>>h[i];
        cin>>a[i];
        cin>>b[i];
    }
    for(int i =0 ;i<n;i++)
    {
        for(int j =0 ;j<n*2;j++)
        {
            tr[0][i][j] = -1;
            tr[1][i][j] = -1;
        }
    }
    for(int i = 0;i<n;i++)
    {
        int mx = -1;
        for(int j= i-1;j>=0;j--)
        {
            if(j + a[j] <= i && i<= j+ b[j] && i-a[i] >= j && j >= i-b[i])
            {
                mx = max(mx,abs(h[i]-h[j]));
            }
            add(0,j,i,mx);
        }
        int mx2 = -1;
        for(int j = i+1;j<n;j++)
        {
            if(i + a[i] <= j && j<= i + b[i] && j-a[j] >=  i&& i >= j-b[j])
            {
                mx2 = max(mx2,abs(h[i]-h[j]));
            }
            add(1,j,i,mx);
        }
    }
    int q;
    cin>>q;
    for(int i =0 ;i<q;i++)
    {
        int l,r;
        cin>>l>>r;
        l--;r--;
        cout<<max(check(0,l,l,r),check(1,r,l,r))<<"\n";
    }
}

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