oj.uz

Submission #47080

# Submission time Handle Problem Language Result Execution time Memory
47080 2018-04-27T09:59:46 Z Alexa2001 trapezoid (balkan11_trapezoid) C++17
60 / 100
 419 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int Mod = 30013, Nmax = 1e5 + 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2800 KB Output is correct
3 Correct 5 ms 2852 KB Output is correct
4 Correct 8 ms 3264 KB Output is correct
5 Correct 8 ms 3632 KB Output is correct
6 Correct 12 ms 3956 KB Output is correct
7 Correct 13 ms 4340 KB Output is correct
8 Correct 19 ms 4836 KB Output is correct
9 Correct 35 ms 6412 KB Output is correct
10 Correct 66 ms 9848 KB Output is correct
11 Correct 84 ms 12040 KB Output is correct
12 Correct 211 ms 20648 KB Output is correct
13 Runtime error 242 ms 36400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 288 ms 42296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 330 ms 46896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 364 ms 51204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 362 ms 55224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 337 ms 60128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 348 ms 64728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 419 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)