#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int ma;
const int N=2*1e6+5;
int m[N];
int n;
int i,k,l0,l,r,r0,nn;
int maxx=INT_MIN;
int res=0;
int hi,lo,mid,d,a;
struct SegmentTree{
void set()
{
a+=n;
m[a]=k;
a>>=1;
for(;a;a>>=1)
m[a]=max(m[2*a],m[2*a+1]);
}
int get()
{
ma=INT_MIN;
for(l0+=n,r0+=n;l0<=r0;l0>>=1,r0>>=1)
{
if(l0%2==1)
{
ma=max(ma,m[l0]);
l0++;
}
if(r0%2==0)
{
ma=max(ma,m[r0]);
r0--;
}
}
return ma;
}
};
int main()
{
SegmentTree m;
//n=1e6;
//scanf("%i",&n);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
assert(n<N);
for(i=0;i<n;i++)
{
//scanf("%i %i",&lo,&hi);
cin >> lo >> hi;
a=i;
k=lo;
m.set();
if(hi<maxx)
{
l++;
r=i;
while(l<r)
{
mid=(l+r)/2;
l0=mid;
r0=i;
d=m.get();
//printf("%i-%i [%i][%i]=%i\n",l,r,mid,i,d);
if(hi<d)
{
l=mid+1;
}
else
{
r=mid;
}
}
l0=l;
r0=i;
maxx=m.get();
}
maxx=max(maxx,lo);
res=max(res,i-l+1);
}
//printf("%i\n",res);
cout << res;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
472 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
660 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
4 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
117 ms |
4352 KB |
Output is correct |
2 |
Correct |
109 ms |
4848 KB |
Output is correct |
3 |
Correct |
129 ms |
5472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
238 ms |
6560 KB |
Output is correct |
2 |
Correct |
224 ms |
7540 KB |
Output is correct |
3 |
Correct |
547 ms |
7608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
263 ms |
7608 KB |
Output is correct |
2 |
Correct |
248 ms |
7636 KB |
Output is correct |
3 |
Correct |
650 ms |
7832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
311 ms |
8420 KB |
Output is correct |
2 |
Correct |
232 ms |
8420 KB |
Output is correct |
3 |
Correct |
800 ms |
9780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
570 ms |
9780 KB |
Output is correct |
2 |
Correct |
403 ms |
18672 KB |
Output is correct |
3 |
Correct |
225 ms |
18672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
182 ms |
18672 KB |
Output is correct |
2 |
Correct |
189 ms |
21804 KB |
Output is correct |
3 |
Correct |
173 ms |
21804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
176 ms |
21804 KB |
Output is correct |
2 |
Correct |
174 ms |
22420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
275 ms |
22420 KB |
Output is correct |
2 |
Correct |
769 ms |
23408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
263 ms |
23408 KB |
Output is correct |
2 |
Correct |
672 ms |
23432 KB |
Output is correct |