#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int a[maxN], b[maxN];
signed main(){
int n;
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i] >> b[i];
}
deque <int> Q;
int i = 1, j = 0;
b[n + 1] = -inf;
int ans = 1;
while (i <= n){
while (!Q.empty() && Q.front() < i) Q.pop_front();
if (j < i){
j = i;
Q.push_back(i);
}
while (j <= n && a[Q.front()] <= b[j + 1]){
++j;
while (!Q.empty() && a[Q.back()] <= a[j]) Q.pop_back();
Q.push_back(j);
}
ans = max(ans, j - i + 1);
++i;
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2492 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2396 KB |
Output is correct |
2 |
Correct |
4 ms |
2652 KB |
Output is correct |
3 |
Correct |
5 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
9800 KB |
Output is correct |
2 |
Correct |
155 ms |
10188 KB |
Output is correct |
3 |
Correct |
172 ms |
10596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
17616 KB |
Output is correct |
2 |
Correct |
362 ms |
18764 KB |
Output is correct |
3 |
Correct |
377 ms |
19768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
445 ms |
22860 KB |
Output is correct |
2 |
Correct |
372 ms |
19020 KB |
Output is correct |
3 |
Correct |
472 ms |
25036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
523 ms |
25804 KB |
Output is correct |
2 |
Correct |
386 ms |
19532 KB |
Output is correct |
3 |
Correct |
583 ms |
30032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
474 ms |
24136 KB |
Output is correct |
2 |
Correct |
351 ms |
18004 KB |
Output is correct |
3 |
Correct |
371 ms |
19208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
12716 KB |
Output is correct |
2 |
Correct |
238 ms |
12872 KB |
Output is correct |
3 |
Correct |
244 ms |
13404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
12112 KB |
Output is correct |
2 |
Correct |
245 ms |
13132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
22216 KB |
Output is correct |
2 |
Correct |
588 ms |
29788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
414 ms |
21588 KB |
Output is correct |
2 |
Correct |
515 ms |
26832 KB |
Output is correct |