Submission #1170018

#TimeUsernameProblemLanguageResultExecution timeMemory
1170018bbartekTwo Antennas (JOI19_antennas)C++20
13 / 100
1199 ms33424 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 2003;

int H[maxn];
int A[maxn];
int B[maxn];
int lewo[maxn][maxn];
int prawo[maxn][maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,q;
    cin>>n;

    int a,b,c;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c;
        H[i] = a;
        A[i] = b;
        B[i] = c;
    }

    for(int i=1;i<=n;i++){
        prawo[i][i] = -1;
        lewo[i][i] = -1;
        for(int j=i+1;j<i+A[i];j++){
            prawo[i][j] = -1; 
        }
        for(int j=i+A[i];j<=i+B[i];j++){
            prawo[i][j] = prawo[i][j-1];
            if(i <= j-A[j] && i >= j-B[j]){
                prawo[i][j] = max(prawo[i][j],abs(H[i]-H[j]));
            }
        }
        for(int j=i+B[i]+1;j<=n;j++){
            prawo[i][j] = prawo[i][j-1];
        }
        for(int j=i-A[i]+1;j<=n;j++){
            lewo[i][j] = -1;
        }
        for(int j=i-A[i];j>=i-B[i];j--){
            lewo[i][j] = lewo[i][j+1];
            if(i >= j+A[j] && i <= j+B[j]){
                lewo[i][j] = max(lewo[i][j],abs(H[i]-H[j]));
            } 
        }
        for(int j=i-B[i]-1;j>=1;j--){
            lewo[i][j] = lewo[i][j+1];
        }
        
    }

    cin>>q;

    int wyn;
    while(q--){
        cin>>a>>b;
        wyn = -1;
        for(int i=a;i<=b;i++){
            wyn = max(wyn,lewo[i][a]);
            wyn = max(wyn,prawo[i][b]);
        }
        cout<<wyn<<"\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...