#include <bits/stdc++.h>
#define ll int
#define MAXN 100010
#define MOD 30013
using namespace std;
struct trapezoid
{
ll a,b,c,d;
};
trapezoid t[MAXN];
bool Cmp(trapezoid x,trapezoid y)
{
return x.a<y.a;
}
map<ll,ll> val;
ll cnt=1,sz=1;
struct element
{
ll maxx,num;
};
element Merge(element x,element y)
{
if (x.maxx>y.maxx)
return x;
if (x.maxx<y.maxx)
return y;
return {x.maxx,x.maxx?x.num+y.num : 1};
}
element neutral={1,0};
struct seg_tree
{
vector<element> st;
void Init()
{
while (sz<cnt)
sz <<= 1;
st.resize(2*sz+2,neutral);
}
void Update(ll pos,element val,ll x,ll lx,ll rx)
{
if (lx==rx)
{
st[x]=Merge(st[x],val);
return;
}
ll mid=(lx+rx)/2;
if (pos<=mid)
Update(pos,val,2*x,lx,mid);
else
Update(pos,val,2*x+1,mid+1,rx);
st[x]=Merge(st[2*x],st[2*x+1]);
}
element Calc(ll l,ll r,ll x,ll lx,ll rx)
{
if (lx>r || rx<l)
return neutral;
if (lx>=l && rx<=r)
return st[x];
ll mid=(lx+rx)/2;
return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
}
};
element ans[MAXN];
vector<ll> toadd[4*MAXN];
seg_tree S;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
set<ll> s;
cin >> n;
for (ll i=1;i<=n;i++)
{
cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
s.insert(t[i].a);
s.insert(t[i].b);
s.insert(t[i].c);
s.insert(t[i].d);
}
sort(t+1,t+1+n,Cmp);
for (ll i : s)
val[i]=cnt++;
for (ll i=1;i<=n;i++)
{
t[i].a=val[t[i].a];
t[i].b=val[t[i].b];
t[i].c=val[t[i].c];
t[i].d=val[t[i].d];
}
ll cur=0;
S.Init();
for (ll i=1;i<=n;i++)
{
while (cur<t[i].a)
{
for (ll ind : toadd[cur])
S.Update(t[ind].d,ans[ind],1,1,sz);
cur++;
}
ans[i]=S.Calc(1,t[i].c,1,1,sz);
if (!ans[i].maxx)
ans[i].num=1;
ans[i].maxx++;
toadd[t[i].d].push_back(i);
}
element anss=neutral;
for (ll i=1;i<=n;i++)
anss=Merge(anss,ans[i]);
cout << anss.maxx << " " << anss.num << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |