#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>v;
bool check(pair<int,int>f,pair<int,int>s){
return abs(f.first-s.first)<=f.second-s.second;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
v.push_back({a,b});
}
stack<pair<int,int>>st;
st.push(v[0]);
for(int i=1;i<n;i++){
int a=v[i].first;
int b=v[i].second;
if(!check(st.top(),v[i])){
while(!st.empty()&&check(v[i],st.top())){
st.pop();
}
st.push(v[i]);
}
}
cout<<st.size();
}
Compilation message
lightningrod.cpp: In function 'int main()':
lightningrod.cpp:18:13: warning: unused variable 'a' [-Wunused-variable]
18 | int a=v[i].first;
| ^
lightningrod.cpp:19:13: warning: unused variable 'b' [-Wunused-variable]
19 | int b=v[i].second;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1195 ms |
262144 KB |
Output is correct |
2 |
Correct |
1191 ms |
262144 KB |
Output is correct |
3 |
Correct |
1172 ms |
261728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
29 ms |
5580 KB |
Output is correct |
15 |
Correct |
29 ms |
5320 KB |
Output is correct |
16 |
Correct |
28 ms |
5320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1228 ms |
227076 KB |
Output is correct |
2 |
Correct |
1226 ms |
226976 KB |
Output is correct |
3 |
Correct |
1187 ms |
221648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1195 ms |
262144 KB |
Output is correct |
2 |
Correct |
1191 ms |
262144 KB |
Output is correct |
3 |
Correct |
1172 ms |
261728 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
456 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
29 ms |
5580 KB |
Output is correct |
18 |
Correct |
29 ms |
5320 KB |
Output is correct |
19 |
Correct |
28 ms |
5320 KB |
Output is correct |
20 |
Correct |
1228 ms |
227076 KB |
Output is correct |
21 |
Correct |
1226 ms |
226976 KB |
Output is correct |
22 |
Correct |
1187 ms |
221648 KB |
Output is correct |
23 |
Correct |
1415 ms |
262144 KB |
Output is correct |
24 |
Correct |
1365 ms |
262144 KB |
Output is correct |
25 |
Correct |
1273 ms |
258340 KB |
Output is correct |