This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Includes */
#include <bits/stdc++.h>
#define se second
#define fi first
/* Using libraries */
using namespace std;
/* Defines */
template <class T>
using vc = vector <T>;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
template <class T>
using pq = priority_queue <T, vector <T>, less <T>>;
template <class T>
using pqr = priority_queue <T, vector <T>, greater <T>>;
#pragma GCC optimize ("03,unroll-loops")
template<class T>
void output(T &a) {
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int inf = 1e18;
const int mod = 1e9 + 7;
const int INF = 1e9;
const int N = 5100;
void solve() {
int n;
cin >> n;
stack <pii> st;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
while (!st.empty() && y - (x - st.top().fi) >= st.top().se) {
st.pop();
}
if (st.empty() || st.top().se - (x - st.top().fi) < y) {
st.push({x, y});
}
}
cout << st.size() << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
while (t--) {
solve();
}
}
/*
1
1 + 2
1 + 2 + 3
*/
Compilation message (stderr)
lightningrod.cpp:45:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
45 | const int inf = 1e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |