#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
const int mx = 8e5 + 9;
bool b1 = true;
bool b2 = true;
bool b4 = true;
int s[mx];
void update(int i, int L, int R, int k, int v) {
if (L == R) {
s[i] = v;
return;
}
int M = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (k <= M) update(x, L, M, k, v);
else update(y, M + 1, R, k, v);
s[i] = max(s[x], s[y]);
return;
}
int query(int i, int L, int R, int l, int r) {
if (L == l && r == R) {
return s[i];
}
int M = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= M) return query(x, L, M, l, r);
else if (M + 1 <= l) return query(y, M + 1, R, l, r);
else return max(query(x, L, M, l, M) , query(y, M + 1, R, M + 1, r));
}
signed main() {
int n; cin >> n;
vector<int> l(n);
vector<int> r(n);
cin >> l[0] >> r[0];
int w;
if(l[0] != r[0]) {
b1 = false;
}
if(l[0] == r[0]) {
w = l[0];
}
if (r[0] != 0) {
b2 = false;
}
if (r[0] > 2) b4 = false;
if (l[0] > 2) b4 = false;
for (int i = 1; i < n; i++) {
cin >> l[i] >> r[i];
if (r[i] != 0) {
b2 = false;
}
if (l[i] != r[i]) {
b1 = false;
}
if(l[i] != w) {
b1 = false;
}
if (r[i] > 2) {
b4 = false;
}
if (l[i] > 2) {
b4 = false;
}
}
int dp[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = 1;
}
int ans = 0;
// //subtask 1
// if (b1) {
// cout << (w + n)/(w + 1);
// return 0;
// }
//
// //subtask 3
// if (n <= 1000) {
// for (int i = 1; i < n; i++) {
// for (int j = 0; j < i - l[i]; j++) {
// if (r[j] < i - j) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
// }
// ans = max(dp[i], ans);
// }
// cout << ans << endl;
// return 0;
// }
//
// //subtask 4
// if (b4) {
// for (int i = 1; i < n; i++) {
// for (int j = max(0ll, i - l[i] - 4) ; j < i - l[i]; j++) {
// if (r[j] < i - j) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
// }
// ans = max(dp[i], ans);
// }
// cout << ans << endl;
// return 0;
// }
//
// subtask 2
if (b2) {
for (int i = 0; i < n; i++) dp[i] = 0;
for (int i = 0; i < n; i++) {
if (i - l[i] < 0) dp[i] = 0;
else if (i - l[i] == 0) dp[i] = 1;
else dp[i] = query(0, 0, n - 1, 0, i - l[i] - 1) + 1;
if (dp[i] > 0) update(0, 0, n - 1, i, dp[i]);
ans = max(ans, dp[i]);
//cout <<"D: " << i << ' ' << dp[i] << endl;
}
cout << ans << endl;
return 0;
}
//subtask 5
cout << ans << endl;
return 1;
}
# | 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... |