Submission #1284649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284649		adscoding	trapezoid (balkan11_trapezoid)	C++20	100 / 100	111 ms	58656 KiB

trapezoid

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define BIT(mask, x) ((mask >> (x)) & 1)
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

/*********************************** CON CUA BO HCN ***********************************/

const int maxn = 1e5 + 3, MOD = 30013;
int n;

struct Tra
{
    int x, y, u, v;
};
Tra a[maxn];

pii dp[maxn];

vector<int> ids;

// Seg: max & cnt

struct Node
{
    int l, r, mx, cnt;
    Node() {l = r = mx = cnt = 0;}
};
Node seg[maxn * 35];
int curNode;

Node combine(Node x, Node y)
{
    Node res;
    if (x.mx < y.mx) swap(x, y);
    res.mx = x.mx;
    res.cnt = x.cnt;
    if (x.mx == y.mx) (res.cnt += y.cnt) %= MOD;
    return res;
}

void upd(int id, int l, int r, int pos, pii val)
{

    if (l == r)
    {
        if (seg[id].mx < val.first) seg[id].mx = val.first, seg[id].cnt = val.second;
        else if (seg[id].mx == val.first) (seg[id].cnt += val.second) %= MOD;
        return;
    }

    int mid = l + r >> 1;
    if (pos <= mid)
    {
        seg[++curNode] = seg[seg[id].l];
        seg[id].l = curNode;
        upd(curNode, l, mid, pos, val);
    }
    else
    {
        seg[++curNode] = seg[seg[id].r];
        seg[id].r = curNode;
        upd(curNode, mid + 1, r, pos, val);
    }

    int tmpl = seg[id].l, tmpr = seg[id].r;
    seg[id] = combine(seg[seg[id].l], seg[seg[id].r]);
    seg[id].l = tmpl;
    seg[id].r = tmpr;
}

Node get(int id, int l, int r, int u, int v)
{
    if (l > v || r < u) return Node();
    if (l >= u && r <= v)
    {
        return seg[id];
    }
    int mid = l + r >> 1;
    return combine(get(seg[id].l, l, mid, u, v), get(seg[id].r, mid + 1, r, u, v));
}

int root[maxn];

void solve()
{
    cin >> n;
    FOR(i, 1, n)
    {
        cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v;
        ids.push_back(a[i].v);
    }

    ids.push_back(-1e9);
    sort(all(ids));
    ids.erase(unique(all(ids)), ids.end());

    sort(a + 1, a + n + 1, [&](const Tra &x, const Tra &y) {
        return x.y < y.y;
    });


    vector<int> Y(n + 1);

    FOR(i, 1, n)
    {
        Y[i] = a[i].y;
        a[i].v = lower_bound(all(ids), a[i].v) - ids.begin();
    }

    int m = (int)ids.size() - 1;

    pii res = {0, 0};

    root[0] = ++curNode;
    upd(root[0], 0, m, 0, {0, 1});

    FOR(i, 1, n)
    {

        root[i] = ++curNode;
        seg[root[i]] = seg[root[i - 1]];

        int pos = lower_bound(Y.begin(), Y.begin() + i, a[i].x) - Y.begin() - 1, it = lower_bound(all(ids), a[i].u) - ids.begin() - 1;

        dp[i] = {1, 1};
        if (it > 0)
        {
            Node cur = get(root[pos], 0, m, 0, it);

            dp[i] = make_pair(cur.mx + 1, cur.cnt);
        }

        if (res.first < dp[i].first) res.first = dp[i].first, res.second = dp[i].second;
        else if (res.first == dp[i].first) (res.second += dp[i].second) %= MOD;

        upd(root[i], 0, m, a[i].v, dp[i]);

    }

    cout << res.first << ' ' << res.second << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    return 0;
}

/* NOTES:
    Ta có thể lấy hai thằng (x1 --> x2, y1 --> y2) và (u1 --> u2, v1 --> v2) khi và chỉ khi u1 > x2 &&  v1 > y2


    seg[id][x]: so thang tai vi tri id 
    sort theo x2 tăng dần

    Sort base on u
*/

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100