#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
/*
const int MOD = ;
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}
*/
using namespace std;
const int MAXN = (int) 1e6;
int l[MAXN + 1], r[MAXN + 1];
int deq[MAXN + 1];
int main() {
//ifstream cin("B.in");
//ofstream cout("B.out");
int i, n;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for(i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
}
int pos = 1, ans = 0;
int be = 0, en = -1;
for(i = 1; i <= n; i++) {
while(pos <= n && (be > en || l[deq[be]] <= r[pos])) {
while(en >= be && l[deq[en]] <= l[pos]) {
en--;
}
deq[++en] = pos++;
}
ans = max(ans, pos - i);
if(deq[be] == i) {
be++;
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
4100 KB |
Output is correct |
2 |
Correct |
76 ms |
4464 KB |
Output is correct |
3 |
Correct |
86 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
6296 KB |
Output is correct |
2 |
Correct |
161 ms |
17940 KB |
Output is correct |
3 |
Correct |
160 ms |
18932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
6652 KB |
Output is correct |
2 |
Correct |
176 ms |
18464 KB |
Output is correct |
3 |
Correct |
201 ms |
24568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
7596 KB |
Output is correct |
2 |
Correct |
180 ms |
19064 KB |
Output is correct |
3 |
Correct |
253 ms |
29968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
197 ms |
7812 KB |
Output is correct |
2 |
Correct |
155 ms |
17612 KB |
Output is correct |
3 |
Correct |
166 ms |
18424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
6648 KB |
Output is correct |
2 |
Correct |
119 ms |
6832 KB |
Output is correct |
3 |
Correct |
119 ms |
12432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
6540 KB |
Output is correct |
2 |
Correct |
127 ms |
12584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
6128 KB |
Output is correct |
2 |
Correct |
249 ms |
29680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
5880 KB |
Output is correct |
2 |
Correct |
213 ms |
26420 KB |
Output is correct |