Submission #112054

#TimeUsernameProblemLanguageResultExecution timeMemory
112054lauzm0Two Antennas (JOI19_antennas)C++14
13 / 100
1353 ms524288 KiB
#include <iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct antenna {
	int l; int r; long long h;
};
 
int main()
{
	int n;
	cin >> n;
	vector<antenna> ant(n); vector<vector<int> >max(n,vector<int>(n,-1));
	for (int i = 0; i < n; i++) {
		cin >> ant[i].h >> ant[i].l >> ant[i].r;
	}

	for(int a = 0 ; a< n-1 ; a++){
		int mxx = -1;
		for(int b = a+1 ; b<n ; b++){
			bool rangealeft = false; bool rangearight = false; bool rangebleft = false; bool rangebright = false;
 
				if (a - ant[a].l >= b && a - ant[a].r <= b) {
					rangealeft = true;
				}
				if (b - ant[b].l >= a && b - ant[b].r <= a) {
					rangebleft = true;
				}
				if (a + ant[a ].l <= b && a + ant[a].r >= b) {
					rangearight = true;
				}
				if (b + ant[b].l <= a && b + ant[b].r >= a) {
					rangebright = true;
				}
				if ((rangealeft||rangearight)&&(rangebleft||rangebright)) {
					if (abs(ant[a ].h - ant[b ].h) > mxx) {
						mxx= abs(ant[a ].h - ant[b ].h);
					}
				}
				max[a][b]=mxx;
		}
	}

	

	int q ; cin>>q; 
	for(int i = 0 ; i< q ; i++){
		int l ; int r; int maxima=-1;
		cin>>l>>r;
		for(int j = l ; j< r ; j++){
			if(max[j-1][r-1]>maxima){
				maxima=max[j-1][r-1];
			}
		}
		cout<<maxima<<endl;
		
	}

	

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...