#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,mod=30013;
struct rect
{
int a,b,c,d;
int id;
};
bool cmp(rect a,rect b)
{
return a.b<b.b;
}
bool cmp_2(rect a,rect b)
{
return a.d<b.d;
}
int n;
rect inp[nmax];
pair<int/*maximum*/,int/*times*/> dp[nmax];
pair<int/*up to*/,int/*original id*/> seen[nmax];
pair<int/*maximum*/,int/*times*/> tree[4*nmax];
pair<int/*maximum*/,int/*times*/> my_merge(pair<int/*maximum*/,int/*times*/> a,pair<int/*maximum*/,int/*times*/> b)
{
if(a.first>b.first)return a;
if(a.first<b.first)return b;
a.second=(a.second+b.second)%mod;
return a;
}
pair<int/*maximum*/,int/*times*/> query(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[node];
pair<int/*maximum*/,int/*times*/> ret={0,0};
int av=(l+r)/2;
if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
return ret;
}
void update(int node,int l,int r,int pos,pair<int/*maximum*/,int/*times*/> val)
{
if(l==r)
{
tree[node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,val);
else update(node*2+1,av+1,r,pos,val);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
int where[nmax];
int main()
{
scanf("%i",&n);
for(int i=1;i<=n;i++)
{
scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
dp[i]={1,1};
}
sort(inp+1,inp+n+1,cmp);
for(int i=1;i<=n;i++)
inp[i].id=i;
for(int i=1;i<=n;i++)
{
int ok=0,not_ok=i;
while(not_ok-ok>1)
{
int av=(ok+not_ok)/2;
if(inp[av].b<inp[i].a)ok=av;
else not_ok=av;
}
seen[i]={ok,i};
//cout<<i<<" -> "<<ok<<" "<<i<<endl;
}
sort(seen+1,seen+n+1);
sort(inp+1,inp+n+1,cmp_2);
for(int i=1;i<=n;i++)
where[inp[i].id]=i;
int j=1;
for(int i=0;i<=n;i++)
{
if(i)
{
int id=i;
int pos=where[id];
update(1,1,n,pos,dp[id]);
}
while(j<=n&seen[j].first==i)
{
int id=seen[j].second;
int pos=where[id];
int ok=0,not_ok=n+1;
while(not_ok-ok>1)
{
int av=(ok+not_ok)/2;
if(inp[av].d<inp[pos].c)ok=av;
else not_ok=av;
}
if(ok==0)dp[id]={1,0};
else
{
dp[id]=query(1,1,n,1,ok);
dp[id].first++;
}
if(dp[id]==make_pair(1,0))dp[id]={1,1};
j++;
//cout<<id<<" -> "<<dp[id].first<<" "<<dp[id].second<<endl;
}
}
//inp[j].d<inp[i].c
int maxi=0,sum=0;
for(int i=1;i<=n;i++)
{
if(dp[i].first>maxi)
{
maxi=dp[i].first;
sum=dp[i].second;
}
else if(dp[i].first==maxi)
{
sum=(sum+dp[i].second)%mod;
}
}
printf("%i %i\n",maxi,sum);
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
while(j<=n&seen[j].first==i)
~^~~
trapezoid.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
trapezoid.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
6 ms |
632 KB |
Output is correct |
| 7 |
Correct |
6 ms |
632 KB |
Output is correct |
| 8 |
Correct |
9 ms |
804 KB |
Output is correct |
| 9 |
Correct |
16 ms |
1224 KB |
Output is correct |
| 10 |
Correct |
27 ms |
2296 KB |
Output is correct |
| 11 |
Correct |
36 ms |
2652 KB |
Output is correct |
| 12 |
Correct |
80 ms |
4728 KB |
Output is correct |
| 13 |
Correct |
98 ms |
5320 KB |
Output is correct |
| 14 |
Correct |
118 ms |
7136 KB |
Output is correct |
| 15 |
Correct |
133 ms |
7388 KB |
Output is correct |
| 16 |
Correct |
142 ms |
7644 KB |
Output is correct |
| 17 |
Correct |
147 ms |
8056 KB |
Output is correct |
| 18 |
Correct |
122 ms |
8312 KB |
Output is correct |
| 19 |
Correct |
146 ms |
8640 KB |
Output is correct |
| 20 |
Correct |
171 ms |
8952 KB |
Output is correct |
