Submission #291804

#	Time	Username	Problem	Language	Result	Execution time	Memory
291804		Plurm	Two Antennas (JOI19_antennas)	C++11	0 / 100	3082 ms	32608 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 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);
	for(auto it = beg; it != end; it++){
		ans.push_back(*it);
	}
	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);
}
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);
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		vector<int> cur;
		int ll = i + l[i];
		int rr = i + r[i];
		if(ll > n) continue;
		ll = min(ll, n);
		rr = min(rr, n);
		query(1, i, ll, rr, cur);
		cnt += cur.size();
	}
	if(cnt > 2*n) while(true);
	return 0;
}

Compilation message (stderr)

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

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