이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) int(v.size())
#define iter(v) v.begin(), v.end()
#define pb emplace_back
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug() { cerr << "\n"; }
template<class T, class ... U>
void debug(T a, U... b) {
cerr << a << " ", debug(b...);
}
template<class T>
void pary(T l, T r){
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
int lowbit(int x) {
return x & -x;
}
struct BIT {
vector<int> bit;
explicit BIT(int n): bit(n + 1) {}
void modify(int x, int v) {
for (; x < SZ(bit); x += lowbit(x))
bit[x] = max(bit[x], v);
}
int query(int x) {
int ans = 0;
for (; x > 0; x -= lowbit(x))
ans = max(ans, bit[x]);
return ans;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
BIT bit(n);
vector<int> l(n + 1), r(n + 1);
for (int i = 1; i <= n; i++)
cin >> l[i] >> r[i];
vector<int> dp(n + 1);
vector<vector<int>> ev(n + 1);
for (int i = 1; i <= n; i++) {
for (int j : ev[i]) bit.modify(j, dp[j]);
dp[i] = bit.query(max(0, i - l[i] - 1)) + 1;
if (i + r[i] + 1 <= n)
ev[i + r[i] + 1].pb(i);
}
cout << *max_element(iter(dp)) << "\n";
}
# | 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... |