| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1171651 | Hanksburger | Game (IOI13_game) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n, cnt1, cnt2, mod=30013;
pair<int, int> combine(pair<int, int> x, pair<int, int> y)
{
if (x.first!=y.first)
return x.first>y.first?x:y;
return {x.first, (x.second+y.second)%mod};
}
struct node2
{
pair<int, int> val;
node2 *lc, *rc;
int l, r;
node2(int l, int r) : val({0, 0}), lc(0), rc(0), l(l), r(r) {}
};
struct node1
{
node1 *lc, *rc;
node2 *x;
node1() : lc(0), rc(0), x(0) {}
};
void update2(node2 *i, int y, pair<int, int> z)
{
if (i->l==i->r)
{
i->val=z;
return;
}
int mid=(i->l+i->r)/2;
if (y<=mid)
{
if (!i->lc)
i->lc=new node2(y, y);
else if (y<i->lc->l || y>i->lc->r)
{
int l=i->l, r=i->r, m=(l+r)/2;
while ((y<=m)^(i->lc->l>m))
{
if (y<=m)
r=m;
else
l=m+1;
m=(l+r)/2;
}
node2 *j=new node2(l, r);
if (y<=m)
j->rc=i->lc;
else
j->lc=i->lc;
i->lc=j;
}
update2(i->lc, y, z);
}
else
{
if (!i->rc)
i->rc=new node2(y, y);
else if (y<i->rc->l || y>i->rc->r)
{
int l=i->l, r=i->r, m=(l+r)/2;
while ((y<=m)^(i->rc->l>m))
{
if (y<=m)
r=m;
else
l=m+1;
m=(l+r)/2;
}
node2 *j=new node2(l, r);
if (y<=m)
j->rc=i->rc;
else
j->lc=i->rc;
i->rc=j;
}
update2(i->rc, y, z);
}
i->val=combine(i->lc?i->lc->val:make_pair(0, 0), i->rc?i->rc->val:make_pair(0, 0));
}
pair<int, int> query2(node2 *i, int ql, int qr)
{
if (ql<=i->l && i->r<=qr)
return i->val;
int mid=(i->l+i->r)/2;
pair<int, int> res={0, 0};
if (i->l<=qr && ql<=mid && i->lc)
res=combine(res, query2(i->lc, ql, qr));
if (mid<qr && ql<=i->r && i->rc)
res=combine(res, query2(i->rc, ql, qr));
return res;
}
void update1(node1 *i, int L, int R, int x, int y, pair<int, int> z)
{
if (L==R)
{
if (!i->x)
i->x=new node2(1, cnt2);
update2(i->x, y, z);
return;
}
int mid=(L+R)/2;
if (x<=mid)
{
if (!i->lc)
i->lc=new node1();
update1(i->lc, L, mid, x, y, z);
}
else
{
if (!i->rc)
i->rc=new node1();
update1(i->rc, mid+1, R, x, y, z);
}
if (!i->x)
i->x=new node2(1, cnt2);
update2(i->x, y, combine(i->lc?query2(i->lc->x, y, y):make_pair(0, 0), i->rc?query2(i->rc->x, y, y):make_pair(0, 0)));
}
pair<int, int> query1(node1 *i, int L, int R, int ql1, int qr1, int ql2, int qr2)
{
if (ql1<=L && R<=qr1)
return query2(i->x, ql2, qr2);
int mid=(L+R)/2;
pair<int, int> res={0, 0};
if (L<=qr1 && ql1<=mid && i->lc)
res=combine(res, query1(i->lc, L, mid, ql1, qr1, ql2, qr2));
if (mid<qr1 && ql1<=R && i->rc)
res=combine(res, query1(i->rc, mid+1, R, ql1, qr1, ql2, qr2));
return res;
}
vector<pair<pair<int, int>, pair<int, int> > > vec;
node1 *root=new node1();
map<int, int> mp1, mp2;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
mp1[0]=mp2[0]=1;
for (int i=0; i<n; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
vec.push_back({{a, b}, {c, d}});
mp1[a]=mp1[b]=mp2[c]=mp2[d]=1;
}
sort(vec.begin(), vec.end());
for (auto it=mp1.begin(); it!=mp1.end(); it++)
it->second=(++cnt1);
for (auto it=mp2.begin(); it!=mp2.end(); it++)
it->second=(++cnt2);
update1(root, 1, cnt1, 1, 1, {0, 1});
for (int i=0; i<n; i++)
{
pair<int, int> res=query1(root, 1, cnt1, 1, mp1[vec[i].first.first]-1, 1, mp2[vec[i].second.first]-1);
res.first++;
update1(root, 1, cnt1, mp1[vec[i].first.second], mp2[vec[i].second.second], res);
}
pair<int, int> ans=query1(root, 1, cnt1, 1, cnt1, 1, cnt2);
cout << ans.first << ' ' << ans.second;
}