#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 2e9;
struct FenwickTree{
vector<int> a; int n, s;
FenwickTree(int N){ a.assign((n=N)+1, -INF); }
void update(int i, int v){
for(++i; i<=n; i+=i&-i) a[i] = max(a[i], v);
}
int get(int i){
s = -INF;
for(++i; i>=1; i-=i&-i) s = max(s, a[i]);
return s;
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
int l[n], r[n];
for(int i=0; i<n; ++i) cin >> l[i] >> r[i];
FenwickTree b(n+1);
vector<int> s;
for(int i=n-1; i>=0; --i){
int low = i, high = n-1;
while(low < high){
int mid = (low + high) / 2;
if(b.get(mid+1) <= -l[i]) low = mid+1;
else high = mid;
}
int j = min(n, low+1);
b.update(i, -r[i]);
r[i] = j - i;
while(!s.empty() and l[s.back()] <= l[i]) s.pop_back();
if(!s.empty() && s.back() < j) r[i] = r[s.back()] + (int)s.back() - i;
s.push_back(i);
}
cout << *max_element(r, r+n);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
460 KB |
Output is correct |
2 |
Correct |
5 ms |
416 KB |
Output is correct |
3 |
Correct |
5 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
6024 KB |
Output is correct |
2 |
Correct |
313 ms |
6788 KB |
Output is correct |
3 |
Correct |
320 ms |
7728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
480 ms |
10568 KB |
Output is correct |
2 |
Correct |
548 ms |
9968 KB |
Output is correct |
3 |
Correct |
449 ms |
10004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
571 ms |
11368 KB |
Output is correct |
2 |
Correct |
439 ms |
10820 KB |
Output is correct |
3 |
Correct |
497 ms |
9796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
708 ms |
11996 KB |
Output is correct |
2 |
Correct |
501 ms |
11588 KB |
Output is correct |
3 |
Correct |
657 ms |
11960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
525 ms |
9796 KB |
Output is correct |
2 |
Correct |
482 ms |
11076 KB |
Output is correct |
3 |
Correct |
463 ms |
10564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
428 ms |
10564 KB |
Output is correct |
2 |
Correct |
437 ms |
10548 KB |
Output is correct |
3 |
Correct |
402 ms |
10248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
453 ms |
9284 KB |
Output is correct |
2 |
Correct |
473 ms |
10296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
496 ms |
9828 KB |
Output is correct |
2 |
Correct |
653 ms |
11588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
536 ms |
9444 KB |
Output is correct |
2 |
Correct |
526 ms |
10336 KB |
Output is correct |