#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[500005], dp2[500005], n;
pi A[500005];
void solve(){
cin >> n;
for(int i = 1; i <= n; i++)cin >> A[i].fi >> A[i].se;
sort(A + 1, A + n + 1);
stack <int> s;
for(int i = 1; i <= n; i++){
while(!s.empty() && A[s.top()].fi - A[s.top()].se >= A[i].fi - A[i].se)s.pop();
dp[i] = (s.empty() ? 0 : dp[s.top()]) + 1;
s.push(i);
}
while(!s.empty())s.pop();
for(int i = n; i >= 1; i--){
while(!s.empty() && A[s.top()].fi + A[s.top()].se <= A[i].fi + A[i].se)s.pop();
dp2[i] = (s.empty() ? 0 : dp2[s.top()]) + 1;
s.push(i);
}
dp2[0] = 1e18;
int ans = 1e18, mn = 1e18;
for(int i = 0; i <= n; i++){
ans = min({ans, dp[i] + mn, dp[i] + dp2[i] - 1, dp[i] + dp2[i + 1]});
mn = min(mn, dp2[i]);
}
cout << ans;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
Main.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
31 ms |
11660 KB |
Output is correct |
3 |
Correct |
50 ms |
13404 KB |
Output is correct |
4 |
Correct |
101 ms |
15736 KB |
Output is correct |
5 |
Correct |
55 ms |
14932 KB |
Output is correct |
6 |
Correct |
121 ms |
19780 KB |
Output is correct |
7 |
Correct |
120 ms |
17780 KB |
Output is correct |
8 |
Correct |
112 ms |
15988 KB |
Output is correct |
9 |
Correct |
93 ms |
16004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4536 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4536 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
31 ms |
11660 KB |
Output is correct |
3 |
Correct |
50 ms |
13404 KB |
Output is correct |
4 |
Correct |
101 ms |
15736 KB |
Output is correct |
5 |
Correct |
55 ms |
14932 KB |
Output is correct |
6 |
Correct |
121 ms |
19780 KB |
Output is correct |
7 |
Correct |
120 ms |
17780 KB |
Output is correct |
8 |
Correct |
112 ms |
15988 KB |
Output is correct |
9 |
Correct |
93 ms |
16004 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4536 KB |
Output is correct |
14 |
Correct |
1 ms |
4696 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |