Submission #1171675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171675		Hanksburger	trapezoid (balkan11_trapezoid)	C++20	65 / 100	475 ms	106756 KiB

trapezoid

#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 node
{
    pair<int, int> val;
    node *lc, *rc;
    int l, r;
    node(int l, int r) : val({0, 0}), lc(0), rc(0), l(l), r(r) {}
    node() {}
} bit[200005];
void upd2(node *i, int y, pair<int, int> z)
{
    if (i->l==i->r)
    {
        i->val=combine(i->val, z);
        return;
    }
    int mid=(i->l+i->r)/2;
    if (y<=mid)
    {
        if (!i->lc)
            i->lc=new node(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;
            }
            node *j=new node(l, r);
            if (y<=m)
                j->rc=i->lc;
            else
                j->lc=i->lc;
            i->lc=j;
        }
        upd2(i->lc, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node(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;
            }
            node *j=new node(l, r);
            if (y<=m)
                j->rc=i->rc;
            else
                j->lc=i->rc;
            i->rc=j;
        }
        upd2(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> qry2(node *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, qry2(i->lc, ql, qr));
    if (mid<qr && ql<=i->r && i->rc)
        res=combine(res, qry2(i->rc, ql, qr));
    return res;
}
void upd1(int x, int y, pair<int, int> z)
{
    for (int i=x; i<=cnt1; i+=i&(-i))
        upd2(&bit[i], y, z);
}
pair<int, int> qry1(int x, int y)
{
    pair<int, int> res={0, 0};
    for (int i=x; i; i-=i&(-i))
        res=combine(res, qry2(&bit[i], 1, y));
    return res;
}
vector<pair<pair<int, int>, pair<int, int> > > vec;
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);
    for (int i=1; i<=cnt1; i++)
    {
        bit[i].val={0, 0};
        bit[i].lc=0;
        bit[i].rc=0;
        bit[i].l=1;
        bit[i].r=cnt2;
    }
    upd1(1, 1, {0, 1});
    for (int i=0; i<n; i++)
    {
        pair<int, int> res=qry1(mp1[vec[i].first.first]-1, mp2[vec[i].second.first]-1);
        res.first++;
        upd1(mp1[vec[i].first.second], mp2[vec[i].second.second], res);
    }
    pair<int, int> ans=qry1(cnt1, cnt2);
    cout << ans.first << ' ' << ans.second;
}

• Subtask 1: 65 / 100