#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,i,ta,tb,tc,td,j,h1,h2,d[101010],d2[101010],mo=30013,K;
vector<int> v[101010];
pair<pair<int,int>,pair<int,int> > A[101010];
map<int,int> BIT;
int depe(int aa)
{
if(d[aa]==-1)
{
d[aa]=0;
int ii;
for(ii=0;ii<v[aa].size();ii++)
d[aa]=max(d[aa],depe(v[aa][ii]));
d[aa]++;
}
return d[aa];
}
int depe2(int aa)
{
if(depe(aa)==1)return 1;
if(d2[aa]==-1)
{
d2[aa]=0;
int ii;
for(ii=0;ii<v[aa].size();ii++)
if(depe(aa)==depe(v[aa][ii])+1)
d2[aa]=(d2[aa]+depe2(v[aa][ii]))%mo;
}
return d2[aa];
}
void upd(int aa,int bb)
{
int ii;
for(ii=aa;ii<=K;ii+=(ii&(-ii)))
BIT[ii]=max(BIT[ii],bb);
}
int que(int aa)
{
int ii,H=0;
for(ii=aa;ii>=1;ii-=(ii&(-ii)))
H=max(H,BIT[ii]);
return H;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
K=1000000001;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>ta>>tb>>tc>>td;
A[i]=mp(mp(ta,tb),mp(tc,td));
}
if(1)
{
sort(A+1,A+1+n);
for(i=1;i<=n;i++)
{
int L=i+1,R=n,C,H=0;
while(L<=R)
{
C=(L+R)/2;
if(A[i].fi.se<A[C].fi.fi)
{
H=C;
R=C-1;
}
else
L=C+1;
}
if(H)
v[H].pb(i);
}
//return 0;
for(i=n;i>=1;i--)
{
for(j=0;j<v[i].size();j++)
{
int now=v[i][j];
ll k;
for(k=i;k<=n;k++)
if(A[now].se.fi<A[k].se.se)
d[now]=max(d[now],d[k]);
// cout<<i<<" "<<now<<" "<<d[now]<<"\n";
}
d[i]++;
upd(A[i].se.fi,d[i]);
h1=max(h1,d[i]);
}
//cout<<h1<<"\n";
}
else
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(A[i].fi.se<A[j].fi.fi&&A[i].se.se<A[j].se.fi)
v[i].pb(j);
memset(d,-1,sizeof(d));
memset(d2,-1,sizeof(d2));
for(i=1;i<=n;i++)
h1=max(h1,depe(i));
for(i=1;i<=n;i++)
if(depe(i)==h1)
h2=(h2+depe2(i))%mo;
}
cout<<h1<<" "<<h2<<"\n";
}
Compilation message
trapezoid.cpp: In function 'int depe(int)':
trapezoid.cpp:18:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'int depe2(int)':
trapezoid.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
4 ms |
2680 KB |
Partially correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
2808 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
3000 KB |
Output isn't correct |
| 6 |
Incorrect |
24 ms |
3192 KB |
Output isn't correct |
| 7 |
Partially correct |
36 ms |
3368 KB |
Partially correct |
| 8 |
Incorrect |
33 ms |
3192 KB |
Output isn't correct |
| 9 |
Incorrect |
166 ms |
3704 KB |
Output isn't correct |
| 10 |
Execution timed out |
639 ms |
5704 KB |
Time limit exceeded |
| 11 |
Execution timed out |
970 ms |
5752 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1087 ms |
6904 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1089 ms |
7544 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1083 ms |
7928 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1078 ms |
7816 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1063 ms |
7884 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1084 ms |
8312 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1079 ms |
7544 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1070 ms |
7288 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1084 ms |
7924 KB |
Time limit exceeded |
