Submission #362217

#	Time	Username	Problem	Language	Result	Execution time	Memory
362217		ngpin04	trapezoid (balkan11_trapezoid)	C++14	100 / 100	121 ms	7764 KiB

trapezoid

#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 / 100