oj.uz

Submission #47081

# Submission time Handle Problem Language Result Execution time Memory
47081 2018-04-27T10:01:34 Z Alexa2001 trapezoid (balkan11_trapezoid) C++17
100 / 100
 486 ms 37760 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5204 KB Output is correct
3 Correct 6 ms 5436 KB Output is correct
4 Correct 7 ms 5524 KB Output is correct
5 Correct 11 ms 5976 KB Output is correct
6 Correct 12 ms 6324 KB Output is correct
7 Correct 16 ms 6740 KB Output is correct
8 Correct 22 ms 7132 KB Output is correct
9 Correct 38 ms 8772 KB Output is correct
10 Correct 75 ms 12160 KB Output is correct
11 Correct 86 ms 14276 KB Output is correct
12 Correct 218 ms 23008 KB Output is correct
13 Correct 283 ms 26284 KB Output is correct
14 Correct 328 ms 29276 KB Output is correct
15 Correct 400 ms 30596 KB Output is correct
16 Correct 412 ms 31980 KB Output is correct
17 Correct 441 ms 33528 KB Output is correct
18 Correct 358 ms 34872 KB Output is correct
19 Correct 414 ms 36208 KB Output is correct
20 Correct 486 ms 37760 KB Output is correct