#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,ST[808080],ST2[808080],D[101010],LZ[808080];
vector<int> v[101010],z;
pair<pair<int,int>,pair<int,int> > A[101010];
map<int,int> me;
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(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
if(LZ[ee])
{
if(aa<bb)
{
LZ[ee*2]=1;
LZ[ee*2+1]=1;
}
LZ[ee]=0;
ST2[ee]=0;
}
if(aa==bb)
{
ST[ee]=dd;
ST2[ee]+=ff;
ST2[ee]%=mo;
}
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)
upd(aa,ce,cc,dd,ee*2,ff);
else
upd(ce+1,bb,cc,dd,ee*2+1,ff);
ST[ee]=max(ST[ee*2],ST[ee*2+1]);
ST2[ee]=(ST2[ee*2]+ST2[ee*2+1])%mo;
}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(bb<cc||dd<aa)return 0;
else
if(cc<=aa&&bb<=dd)return ST[ee];
else
{
ll ce=(aa+bb)/2;
return max(que(aa,ce,cc,dd,ee*2),que(ce+1,bb,cc,dd,ee*2+1));
}
}
ll que2(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(LZ[ee])
{
if(aa<bb)
{
LZ[ee*2]=1;
LZ[ee*2+1]=1;
}
LZ[ee]=0;
ST2[ee]=0;
}
if(bb<cc||dd<aa)return 0;
else
if(cc<=aa&&bb<=dd)return ST2[ee];
else
{
ll ce=(aa+bb)/2;
return ((que2(aa,ce,cc,dd,ee*2)+que2(ce+1,bb,cc,dd,ee*2+1))%mo);
}
}
void kos(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(LZ[ee])
{
if(aa<bb)
{
LZ[ee*2]=1;
LZ[ee*2+1]=1;
}
LZ[ee]=0;
ST2[ee]=0;
}
if(bb<cc||dd<aa)return ;
else
if(cc<=aa&&bb<=dd)
{
ST2[ee]=0;
if(aa<bb)
{
LZ[ee*2]=0;
LZ[ee*2+1]=0;
}
}
else
{
ll ce=(aa+bb)/2;
kos(aa,ce,cc,dd,ee*2);
kos(ce+1,bb,cc,dd,ee*2+1);
ST2[ee]=(ST2[ee*2]+ST2[ee*2+1])%mo;
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
K=n*2;
for(i=1;i<=n;i++)
{
cin>>ta>>tb>>tc>>td;
A[i]=mp(mp(ta,tb),mp(tc,td));
z.pb(tc);
z.pb(td+1);
}
sort(z.begin(),z.end());
for(i=0;i<z.size();i++)
me[z[i]]=i+1;
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--)d[i]=1;
for(i=n;i>=1;i--)d2[i]=1;
for(i=n;i>=1;i--)
{
if(que(1,K,me[A[i].se.fi],K,1)<=d[i])
{
ll L=K+1,R=me[A[i].se.fi],C,H=-1;
R=0;
while(L<=R)
{
C=(L+R)/2;
if(que(1,K,C,me[A[i].se.fi],1)<d[i])
{
H=C;
R=C-1;
}
else
L=C+1;
}
for(j=i;j<=n;j++)
if(A[j].se.fi<A[i].se.fi&&d[j]<d[i])
{
L=min(L,me[A[j].se.fi]);
R=max(R,me[A[j].se.fi]);
}
//if(H!=-1)
kos(1,K,L,R,1);
//cout<<i<<" "<<me[A[i].se.fi]<<" "<<H<<"_\n";
//cout<<"upd "<<i<<" "<<me[A[i].se.fi]<<" "<<d[i]<<"___\n";
upd(1,K,me[A[i].se.fi],d[i],1,d2[i]);
}
for(j=0;j<v[i].size();j++)
{
int now=v[i][j];
d[now]=que(1,K,me[A[now].se.se+1],K,1)+1;
ll L=me[A[now].se.se+1],R=K,C,H=0;
while(L<=R)
{
C=(L+R)/2;
if(que(1,K,me[A[now].se.se+1],C,1)+1==d[now])
{
H=C;
R=C-1;
}
else
L=C+1;
}
L=H,R=K;
ll H2=K;
while(L<=R)
{
C=(L+R)/2;
if((que(1,K,C,K,1)+1)!=d[now])
{
H2=C-1;
R=C-1;
}
else
L=C+1;
}
if(d[now]==1)d2[now]=1;
else
{
// cout<<now<<"___ "<<H<<" "<<H2<<"@\n";
d2[now]=que2(1,K,H,H2,1);
}
}
// cout<<i<<" "<<d[i]<<" "<<d2[i]<<"\n";
h1=max(h1,d[i]);
}
// cout<<"A";
for(i=1;i<=n;i++)
if(h1==d[i])
h2=(h2+d2[i])%mo;
}
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:142:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<z.size();i++)
~^~~~~~~~~
trapezoid.cpp:187:29: error: no matching function for call to 'min(ll&, std::map<int, int>::mapped_type&)'
L=min(L,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
min(const _Tp& __a, const _Tp& __b)
^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: template argument deduction/substitution failed:
trapezoid.cpp:187:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type {aka int}')
L=min(L,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: template argument deduction/substitution failed:
trapezoid.cpp:187:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type {aka int}')
L=min(L,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
min(initializer_list<_Tp> __l)
^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
trapezoid.cpp:187:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
L=min(L,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
min(initializer_list<_Tp> __l, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
trapezoid.cpp:187:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
L=min(L,me[A[j].se.fi]);
^
trapezoid.cpp:188:29: error: no matching function for call to 'max(ll&, std::map<int, int>::mapped_type&)'
R=max(R,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
max(const _Tp& __a, const _Tp& __b)
^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: template argument deduction/substitution failed:
trapezoid.cpp:188:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type {aka int}')
R=max(R,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: template argument deduction/substitution failed:
trapezoid.cpp:188:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type {aka int}')
R=max(R,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
max(initializer_list<_Tp> __l)
^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: template argument deduction/substitution failed:
trapezoid.cpp:188:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
R=max(R,me[A[j].se.fi]);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from trapezoid.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
max(initializer_list<_Tp> __l, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
trapezoid.cpp:188:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
R=max(R,me[A[j].se.fi]);
^
trapezoid.cpp:196:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
