#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int ma;
const int N=2*1e6;
int m[N];
struct SegmentTree{
int n;
void init(int nn)
{
n=nn;
for(int i=0;i<N;i++)
m[i]=INT_MIN;
}
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);
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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
tem.cpp:59: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 |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8316 KB |
Output is correct |
3 |
Correct |
9 ms |
8316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8316 KB |
Output is correct |
2 |
Correct |
9 ms |
8316 KB |
Output is correct |
3 |
Correct |
9 ms |
8340 KB |
Output is correct |
4 |
Correct |
9 ms |
8472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8472 KB |
Output is correct |
2 |
Correct |
13 ms |
8472 KB |
Output is correct |
3 |
Correct |
12 ms |
8516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
8524 KB |
Output is correct |
2 |
Correct |
128 ms |
8528 KB |
Output is correct |
3 |
Correct |
151 ms |
8528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
287 ms |
8592 KB |
Output is correct |
2 |
Correct |
272 ms |
19852 KB |
Output is correct |
3 |
Correct |
626 ms |
20068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
20068 KB |
Output is correct |
2 |
Correct |
319 ms |
23300 KB |
Output is correct |
3 |
Correct |
735 ms |
23300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
374 ms |
23392 KB |
Output is correct |
2 |
Runtime error |
315 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. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
703 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 |
195 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 |
188 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 |
332 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 |
281 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 |
- |