oj.uz

Submission #362217

# Submission time Handle Problem Language Result Execution time Memory
362217 2021-02-02T08:14:45 Z ngpin04 trapezoid (balkan11_trapezoid) C++14
100 / 100
 121 ms 7764 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
struct trapezoid
{
    int l,r,u,v;
};

const int N = 1e5 + 5;
const int mod = 30013;

trapezoid a[N];

vector <int> id;

pair <int, int> bit[2 * N];
pair <int, int> dp[N];

int n;

pair <int, int> operator + (const pair <int, int> &a, const pair <int, int> &b)
{
    if (a.fi < b.fi)
        return b;
    if (a.fi > b.fi)
        return a;
    return mp(a.fi, (a.se + b.se) % mod);
}

void operator += (pair <int, int> &a, const pair <int, int> &b)
{
    a = a + b;
}

void update(int pos, pair <int, int> val)
{
    for (; pos <= 2 * n; pos += pos & -pos)
        bit[pos] += val;
}

pair <int, int> getsum(int pos)
{
    pair <int, int> res = mp(0, 0);
    for (; pos > 0; pos -= pos & -pos)
        res += bit[pos];
    return res;
}

int getpos(int x, vector <int> &val)
{
    return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

void compress()
{
    vector <int> val;

    for (int i = 1; i <= n; i++)
    {
        val.push_back(a[i].u);
        val.push_back(a[i].v);
    }
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());

    for (int i = 1; i <= n; i++)
    {
        a[i].u = getpos(a[i].u, val);
        a[i].v = getpos(a[i].v, val);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].l >> a[i].r >> a[i].u >> a[i].v;

    for (int i = 1; i <= n; i++)
        id.push_back(i), id.push_back(-i);

    sort(id.begin(), id.end(), [](int i, int j)
     {
        int x = (i > 0) ? (a[i].r) : (a[-i].l);
        int y = (j > 0) ? (a[j].r) : (a[-j].l);
        return x < y;
     });

    compress();

    for (int i : id)
    {
        if (i < 0)
        {
            i *= -1;
            dp[i] = getsum(a[i].u);
            dp[i].fi++;
            if (dp[i].fi == 1)
                dp[i].se++;
        } else
            update(a[i].v, dp[i]);
    }

    pair <int, int> ans = mp(0, 0);
    for (int i = 1; i <= n; i++)
        ans += dp[i];
    cout << ans.fi << " " << ans.se;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 11 ms 1180 KB Output is correct
10 Correct 22 ms 1916 KB Output is correct
11 Correct 27 ms 2344 KB Output is correct
12 Correct 58 ms 4192 KB Output is correct
13 Correct 72 ms 4884 KB Output is correct
14 Correct 104 ms 5748 KB Output is correct
15 Correct 96 ms 6052 KB Output is correct
16 Correct 101 ms 6384 KB Output is correct
17 Correct 104 ms 6888 KB Output is correct
18 Correct 102 ms 7076 KB Output is correct
19 Correct 107 ms 7292 KB Output is correct
20 Correct 121 ms 7764 KB Output is correct