#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(0);
cin.tie(nullptr);
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 |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
2 |
Correct |
2 ms |
624 KB |
Output is correct |
3 |
Correct |
2 ms |
624 KB |
Output is correct |
4 |
Correct |
2 ms |
712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
736 KB |
Output is correct |
2 |
Correct |
5 ms |
812 KB |
Output is correct |
3 |
Correct |
5 ms |
868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
110 ms |
4368 KB |
Output is correct |
2 |
Correct |
126 ms |
4896 KB |
Output is correct |
3 |
Correct |
127 ms |
5408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
223 ms |
6560 KB |
Output is correct |
2 |
Correct |
235 ms |
7032 KB |
Output is correct |
3 |
Correct |
575 ms |
7132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
269 ms |
7132 KB |
Output is correct |
2 |
Correct |
255 ms |
7384 KB |
Output is correct |
3 |
Correct |
656 ms |
7464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
320 ms |
8144 KB |
Output is correct |
2 |
Correct |
246 ms |
8144 KB |
Output is correct |
3 |
Correct |
836 ms |
9112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
581 ms |
9112 KB |
Output is correct |
2 |
Correct |
415 ms |
18228 KB |
Output is correct |
3 |
Correct |
242 ms |
18228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
183 ms |
18228 KB |
Output is correct |
2 |
Correct |
214 ms |
22304 KB |
Output is correct |
3 |
Correct |
187 ms |
22304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
181 ms |
22328 KB |
Output is correct |
2 |
Correct |
189 ms |
23128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
260 ms |
23128 KB |
Output is correct |
2 |
Correct |
819 ms |
29236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
257 ms |
29236 KB |
Output is correct |
2 |
Runtime error |
743 ms |
33792 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |