#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];
struct SegmentTree{
int n;
void init(int nn)
{
n=nn;
}
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)
{
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);
assert(n<N);
m.init(n);
int l=0;
int maxx=INT_MIN;
int res=0;
int hi,lo,r,mid,d;
for(int i=0;i<n;i++)
{
scanf("%i %i",&lo,&hi);
m.set(i,lo);
if(hi<maxx)
{
l++;
r=i;
while(l<r)
{
mid=(l+r)/2;
d=m.get(mid,i);
//printf("%i-%i [%i][%i]=%i\n",l,r,mid,i,d);
if(hi<d)
{
l=mid+1;
}
else
{
r=mid;
}
}
maxx=m.get(l,i);
}
maxx=max(maxx,lo);
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:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
tem.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&lo,&hi);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
528 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
3 ms |
708 KB |
Output is correct |
4 |
Correct |
2 ms |
708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
748 KB |
Output is correct |
2 |
Correct |
6 ms |
976 KB |
Output is correct |
3 |
Correct |
5 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
170 ms |
4396 KB |
Output is correct |
2 |
Correct |
133 ms |
5008 KB |
Output is correct |
3 |
Correct |
178 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
6728 KB |
Output is correct |
2 |
Correct |
326 ms |
8804 KB |
Output is correct |
3 |
Correct |
601 ms |
9000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
328 ms |
9000 KB |
Output is correct |
2 |
Correct |
302 ms |
9184 KB |
Output is correct |
3 |
Correct |
689 ms |
9184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
436 ms |
9684 KB |
Output is correct |
2 |
Correct |
317 ms |
21540 KB |
Output is correct |
3 |
Runtime error |
936 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. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
619 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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
194 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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
200 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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
331 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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
291 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 |
- |