Submission #105842

#	Time	Username	Problem	Language	Result	Execution time	Memory
105842		Pro_ktmr	Two Antennas (JOI19_antennas)	C++14	13 / 100	205 ms	10288 KiB

antennas

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

struct RMQ{
private:
	int N;
	vector<LL> node;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		for(int i=0; i<2*N-1; i++) node.PB(-1);
	}
	void update(int k, LL x){
		k += N-1;
		node[k] = max(node[k], x);
		while(k > 0){
			k = (k-1)/2;
			node[k] = max(node[2*k+1],node[2*k+2]);
		}
	}
	LL sum(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return -1;
		if(a <= l && r <= b) return node[k];
		return max(sum(a, b, 2*k+1, l, (l+r)/2),sum(a, b, 2*k+2, (l+r)/2, r));
	}
};

int N,H[200000],A[200000],B[200000],Q,L[200000],R[200000];
vector<pair<pair<int,int>,int>> v,q;
int ans[200000];
int main(){
	scanf("%d", &N);
	if(N > 2000) return -1;
	for(int i=0; i<N; i++){
		scanf("%d%d%d", H+i, A+i, B+i);
	}
	
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			int d = j-i;
			if(d < A[i] || d < A[j] || B[i] < d || B[j] < d) continue;
			v.PB(MP(MP(i+1,j+1),abs(H[i]-H[j])));
		}
	}
	sort(v.begin(), v.end());
	
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		scanf("%d%d", L+i, R+i);
		q.PB(MP(MP(L[i],R[i]),i));
	}
	sort(q.begin(), q.end());
	
	RMQ rsq;
	rsq.init(N+1);
	
	int now = v.size()-1;
	for(int i=Q-1; i>=0; i--){
		while(now >= 0 && v[now].first.first >= q[i].first.first){
			rsq.update(v[now].first.second, v[now].second);
			now--;
		}
		ans[q[i].second] = rsq.sum(q[i].first.first, q[i].first.second+1);
	}
	
	for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
	
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", H+i, A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", L+i, R+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

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