#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);
assert(n<N);
for(i=0;i<n;i++)
{
scanf("%i %i",&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);
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:53: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 |
452 KB |
Output is correct |
2 |
Correct |
2 ms |
452 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
540 KB |
Output is correct |
2 |
Correct |
2 ms |
544 KB |
Output is correct |
3 |
Correct |
2 ms |
676 KB |
Output is correct |
4 |
Correct |
2 ms |
676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
716 KB |
Output is correct |
2 |
Correct |
5 ms |
780 KB |
Output is correct |
3 |
Correct |
5 ms |
864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
4400 KB |
Output is correct |
2 |
Correct |
128 ms |
4916 KB |
Output is correct |
3 |
Correct |
146 ms |
5632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
6720 KB |
Output is correct |
2 |
Correct |
279 ms |
8856 KB |
Output is correct |
3 |
Correct |
603 ms |
9020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
320 ms |
9020 KB |
Output is correct |
2 |
Correct |
286 ms |
9128 KB |
Output is correct |
3 |
Correct |
766 ms |
9188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
372 ms |
9840 KB |
Output is correct |
2 |
Correct |
292 ms |
16656 KB |
Output is correct |
3 |
Correct |
858 ms |
18092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
628 ms |
18092 KB |
Output is correct |
2 |
Correct |
613 ms |
26952 KB |
Output is correct |
3 |
Runtime error |
308 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 |
191 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 |
192 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 |
302 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 |
297 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 |
- |