#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e6 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n;
int ad[MAXN], au[MAXN];
int inf = -1e9-10;
void read()
{
cin >> n;
int xx, yy;
for (int i = 1; i <= n; ++ i)
{
cin >> ad[i] >> au[i];
}
}
int t[MAXN * 4];
void make_tree(int i, int l, int r)
{
if(l == r)
{
t[i] = ad[l];
return;
}
int mid = (l + r)/2;
make_tree(2*i, l, mid);
make_tree(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
}
int ql, qr;
int query(int i, int l, int r)
{
if(qr < l || ql > r)return inf;
if(ql <= l && r <= qr)return t[i];
int mid = (l + r)/2;
return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
int main()
{
speed();
read();
make_tree(1, 1, n);
int ans = 0;
int last = 1;
for (int i = 1; i <= n; ++ i)
{
int left = last, right = i, mid, border = i;
while(left <= right)
{
mid = (left + right)/2;
ql = mid;
qr = i;
int maxx = query(1, 1, n);
if(maxx > au[i])
{
left = mid + 1;
}
else
{
border = mid;
right = mid - 1;
}
}
last = border;
//cout << i << " " << border << endl;
ans = max(ans, i - border + 1);
}
cout << ans << endl;
return 0;
}
Compilation message
tem.cpp: In function 'void read()':
tem.cpp:17:9: warning: unused variable 'xx' [-Wunused-variable]
17 | int xx, yy;
| ^~
tem.cpp:17:13: warning: unused variable 'yy' [-Wunused-variable]
17 | int xx, yy;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4700 KB |
Output is correct |
2 |
Correct |
22 ms |
4780 KB |
Output is correct |
3 |
Correct |
25 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1044 ms |
15700 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1016 ms |
27336 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1030 ms |
32596 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1022 ms |
35552 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1020 ms |
33608 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1040 ms |
22096 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1042 ms |
21824 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1004 ms |
32088 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1040 ms |
31552 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |