#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3082 ms |
12672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3082 ms |
12672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
32608 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3082 ms |
12672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
