Submission #1171627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171627		Hanksburger	trapezoid (balkan11_trapezoid)	C++20	45 / 100	468 ms	131072 KiB

trapezoid

#include <bits/stdc++.h>
#define int long long
using namespace std;
int large=1e9, 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;
    int l, r;
    node1(int l, int r) : lc(0), rc(0), x(0), l(l), r(r) {}
};
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(0LL, 0LL), i->rc?i->rc->val:make_pair(0LL, 0LL));
}
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 x, int y, pair<int, int> z)
{
    if (i->l==i->r)
    {
        if (!i->x)
            i->x=new node2(0, large);
        update2(i->x, y, z);
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node1(i->l, mid);
        update1(i->lc, x, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node1(mid+1, i->r);
        update1(i->rc, x, y, z);
    }
    if (!i->x)
        i->x=new node2(0, large);
    update2(i->x, y, combine(i->lc?query2(i->lc->x, y, y):make_pair(0LL, 0LL), i->rc?query2(i->rc->x, y, y):make_pair(0LL, 0LL)));
}
pair<int, int> query1(node1 *i, int ql1, int qr1, int ql2, int qr2)
{
    if (ql1<=i->l && i->r<=qr1)
        return query2(i->x, ql2, qr2);
    int mid=(i->l+i->r)/2;
    pair<int, int> res={0, 0};
    if (i->l<=qr1 && ql1<=mid && i->lc)
        res=combine(res, query1(i->lc, ql1, qr1, ql2, qr2));
    if (mid<qr1 && ql1<=i->r && i->rc)
        res=combine(res, query1(i->rc, ql1, qr1, ql2, qr2));
    return res;
}
vector<pair<pair<int, int>, pair<int, int> > > vec;
node1 *root=new node1(0, large);
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.push_back({{a, b}, {c, d}});
    }
    sort(vec.begin(), vec.end());
    update1(root, 0, 0, {0, 1});
    for (int i=0; i<n; i++)
    {
        pair<int, int> res=query1(root, 0, vec[i].first.first-1, 0, vec[i].second.first-1);
        res.first++;
        update1(root, vec[i].first.second, vec[i].second.second, res);
    }
    pair<int, int> ans=query1(root, 0, large, 0, large);
    cout << ans.first << ' ' << ans.second;
}

• Subtask 1: 45 / 100