Submission #291835

#	Time	Username	Problem	Language	Result	Execution time	Memory
291835		Plurm	Two Antennas (JOI19_antennas)	C++11	0 / 100	3098 ms	33528 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
int h[200005];
int l[200005];
int r[200005];
vector<int> seg[524288];
int lb[524288];
int rb[524288];
void build(int c, int l, int r){
	lb[c] = l;
	rb[c] = r;
	if(l == r) return;
	int k = (l + r)/2;
	build(2*c, l, k);
	build(2*c+1, k+1, r);
}
void update(int c, int l, int r, int i){
	// Left segment of i-th antenna is l to r
	if(lb[c] == l && rb[c] == r){
		seg[c].push_back(i);
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		update(2*c, l, k, i);
		update(2*c+1, k+1, r, i);
	}else if(r <= k){
		update(2*c, l, r, i);
	}else{
		update(2*c+1, l, r, i);
	}
}
void clean(int c){
	sort(seg[c].begin(), seg[c].end());
	if(lb[c] == rb[c]) return;
	clean(2*c);
	clean(2*c+1);
}
void query(int c, int i, int l, int r, vector<int>& ans){
	auto beg = lower_bound(seg[c].begin(), seg[c].end(), l);
	auto end = upper_bound(seg[c].begin(), seg[c].end(), r);
	if(beg != end){
		int mxh = -1;
		int mnh = 1e9+1;
		int mxidx, mnidx;
		for(auto it = beg; it != end; it++){
			if(h[*it] > mxh){
				mxh = h[*it];
				mxidx = *it;
			}
			if(h[*it] < mnh){
				mnh = h[*it];
				mnidx = *it;
			}
		}
		if(mxidx > mnidx) swap(mxidx, mnidx);
		ans.push_back(mxidx);
		if(mnidx != mxidx) ans.push_back(mnidx);
	}
	if(lb[c] == rb[c]) return;
	int k = (lb[c] + rb[c])/2;
	if(i <= k) query(2*c, i, l, r, ans);
	else query(2*c+1, i, l, r, ans);
}
map<int, int> comms; // (r, d)
vector<pair<int,int> > queries[200005];
int ans[200005];
int main(){
	int n;
	scanf("%d",&n);
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d%d",h+i,l+i,r+i);
		int ll = i - r[i];
		int rr = i - l[i];
		if(rr < 1) continue;
		ll = max(ll, 1);
		rr = max(rr, 1);
		update(1, ll, rr, i);
	}
	clean(1);
	int q;
	scanf("%d",&q);
	for(int i = 1; i <= q; i++){
		int l, r;
		scanf("%d%d",&l,&r);
		queries[l].emplace_back(r, i);
	}
	for(int i = n; i > 0; i--){
		int ll = i + l[i];
		int rr = i + r[i];
		if(ll <= n){
			vector<int> cur;
			ll = min(ll, n);
			rr = min(rr, n);
			query(1, i, ll, rr, cur);
			for(int x : cur){
				// i -- x is a valid communication
				int d = abs(h[i] - h[x]);
				auto it = comms.lower_bound(x);
				bool chk = false;
				if(it != comms.begin()){
					auto pit = it;
					pit--;
					if(pit->second < d) chk = true;
				}else chk = true;
				if(!chk) continue;
				while(it != comms.end() && d >= it->second){
					it = comms.erase(it);
				}
				if(it == comms.end() || it->first != x) comms[x] = d;
			}
		}
		for(auto p : queries[i]){
			int x = p.first;
			int qidx = p.second;
			auto it = comms.upper_bound(x);
			if(it == comms.begin()){
				ans[qidx] = -1;
				continue;
			}
			it--;
			ans[qidx] = it->second;
		}
	}
	for(int i = 1; i <= q; i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
antennas.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d%d%d",h+i,l+i,r+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
antennas.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~

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