Submission #47081

#	Time	Username	Problem	Language	Result	Execution time	Memory
47081		Alexa2001	trapezoid (balkan11_trapezoid)	C++17	100 / 100	486 ms	37760 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int Mod = 30013, Nmax = 2e5 + 5;

map<int,int> mp1, mp2;
int n, i, cnt1 = 1, cnt2 = 1, x, y, z, t;

struct trapezoid
{
    int s, f, x, y;
} a[Nmax];
vector< pair<int,int> > event[Nmax];

struct valuare
{
    int val, ways;
} dp[Nmax];

void combine(valuare &a, valuare b)
{
    if(b.val > a.val) a = b;
        else if(b.val == a.val)
        {
            a.ways += b.ways;
            if(a.ways >= Mod) a.ways -= Mod;
        }
}

class AIB
{
    valuare a[Nmax];
    int ub(int x) { return (x&(-x)); }

    public:
        void update(valuare w, int pos)
        {
            for(; pos<=cnt2; pos+=ub(pos))
                combine(a[pos], w);
        }

        valuare query(int pos)
        {
            valuare ans = {0, 0};
            for(; pos; pos-=ub(pos))
                combine(ans, a[pos]);
            return ans;
        }
} aib;

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> x >> y >> z >> t;
        mp1[x] = mp1[y] = 1;
        mp2[z] = mp2[t] = 1;
        a[i] = {x, y, z, t};
    }

    for(auto &it : mp1) it.second = ++cnt1;
    for(auto &it : mp2) it.second = ++cnt2;

    for(i=1; i<=n; ++i)
        a[i].s = mp1[a[i].s], a[i].f = mp1[a[i].f], a[i].x = mp2[a[i].x], a[i].y = mp2[a[i].y];

    for(i=1; i<=n; ++i) event[a[i].s].push_back({ i, 0 });
    for(i=1; i<=n; ++i) event[a[i].f].push_back({ i, 1 });

    aib.update({0,1}, 1);
    for(i=2; i<=cnt1; ++i)
        for(auto el : event[i])
        {
            int e = el.first;
            if(el.second == 0)
                dp[e] = aib.query(a[e].x - 1), dp[e].val++;
            else aib.update(dp[e], a[e].y);
        }

    valuare ans = {0,1};
    for(i=1; i<=n; ++i)
        combine(ans, dp[i]);

    cout << ans.val << ' ' << ans.ways << '\n';
    return 0;
}

• Subtask 1: 100 / 100