#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1e6+5;
vector<int> lo(N),hi(N);
struct SegmentTree{
vector<int> m;
int n;
void init(int nn)
{
n=nn;
m.resize(2*n);
for(int i=n;i<2*n;i++)
m[i]=lo[i-n];
for(int j=n-1;j>0;j--)
m[j]=max(m[2*j],m[2*j+1]);
}
void set(int i,int k)
{
i+=n;
m[i]=k;
i>>=1;
for(;i;i>>=1)
m[i]=max(m[2*i],m[2*i+1]);
}
int get(int l,int r)
{
int ma=INT_MIN;
for(l+=n,r+=n;l<=r;l>>=1,r>>=1)
{
if(l%2==1)
{
ma=max(ma,m[l]);
l++;
}
if(r%2==0)
{
ma=max(ma,m[r]);
r--;
}
}
return ma;
}
};
int main()
{
SegmentTree m;
int n;
scanf("%i",&n);
for(int i=0;i<n;i++)
scanf("%i %i",&lo[i],&hi[i]);
m.init(n);
int l=0;
int maxx=INT_MIN;
int res=0;
for(int i=0;i<n;i++)
{
if(hi[i]<maxx)
{
l++;
int r=i;
while(l<r)
{
int mid=(l+r)/2;
int d=m.get(mid,i);
//printf("%i-%i [%i][%i]=%i\n",l,r,mid,i,d);
if(hi[i]<d)
{
l=mid+1;
}
else
{
r=mid;
}
}
maxx=m.get(l,i);
}
maxx=max(maxx,lo[i]);
res=max(res,i-l+1);
//printf("%i-%i %i %i\n",l,i,maxx,res);
}
printf("%i\n",res);
return 0;
}
Compilation message
tem.cpp: In function 'int main()':
tem.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
tem.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&lo[i],&hi[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8312 KB |
Output is correct |
3 |
Correct |
10 ms |
8312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8312 KB |
Output is correct |
2 |
Correct |
9 ms |
8352 KB |
Output is correct |
3 |
Correct |
9 ms |
8356 KB |
Output is correct |
4 |
Correct |
9 ms |
8360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8508 KB |
Output is correct |
2 |
Correct |
14 ms |
8572 KB |
Output is correct |
3 |
Correct |
13 ms |
8788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
15144 KB |
Output is correct |
2 |
Correct |
118 ms |
19336 KB |
Output is correct |
3 |
Correct |
128 ms |
23672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
220 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
307 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
342 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
590 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
163 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
168 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
278 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. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
262 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. |
2 |
Halted |
0 ms |
0 KB |
- |