Submission #391652

#	Time	Username	Problem	Language	Result	Execution time	Memory
391652		egod1537	trapezoid (balkan11_trapezoid)	C++14	100 / 100	273 ms	35448 KiB

trapezoid

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
const int MOD = 30013;
typedef pair<int, int> pi;

struct Line {
    int u, d, idx;
    bool end;
};

struct Seg {
    int n;
    vector<pi> seg;
    void Init(int _n) {
        n = _n;
        seg.resize(4*n);
    }
    pi merge(pi a, pi b) {
        if (a.first != b.first) return max(a, b);
        return pi(a.first, (a.second+b.second)%MOD);
    }

    pi update(int num, int s, int e, int idx, pi diff) {
        if (idx < s || e < idx) return seg[num];
        if (s == e) return seg[num] = diff;

        int mid = s + e >> 1;
        return seg[num] = 
            merge(update(2*num, s, mid, idx, diff), update(2*num+1, mid+1, e, idx, diff));
    }
    void update(int idx, pi diff) { update(1, 0, n-1, idx, diff); }

    pi query(int num, int s, int e, int l, int r) {
        if (r < s || e < l) return { 0, 0 };
        if (l <= s && e <= r) return seg[num];

        int mid = s + e >> 1;
        return merge(query(2*num, s, mid, l, r), query(2*num+1, mid+1, e, l, r));
    }
    pi query(int l, int r) { return query(1, 0, n-1, l, r); }
}tree;



pi dp[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n; cin >> n;
    vector<Line> arr;

    vector<int> sx;
    unordered_map<int, int> xidx;
    for (int i = 0; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        if (a > b)swap(a, b);
        if (c > d) swap(c, d);
        arr.push_back({ a, c, i, false });
        arr.push_back({ b, d, i, true });
        sx.push_back(a); sx.push_back(b);
        sx.push_back(c); sx.push_back(d);
    }
    sort(sx.begin(), sx.end());

    int idx = 0;
    for (int w : sx) xidx[w] = idx++;
    sort(arr.begin(), arr.end(), [&](Line& a, Line& b) -> bool {
        if (a.u != b.u) return a.u < b.u;
        if (a.d != b.d) return a.d < b.d;
        return a.end < b.end;
        });

    tree.Init(idx);
    for (int i = 0; i < arr.size(); i++) {
        int now = arr[i].idx;
        if (!arr[i].end) {
            pi p = tree.query(0, xidx[arr[i].d]);
            dp[now] = { p.first + 1, (p.second==0?1:p.second) };
        }
        else
            tree.update(xidx[arr[i].d], dp[arr[i].idx]);
    }

    int mx = 0;
    for (int i = 0; i < n; i++) mx = max(mx, dp[i].first);
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (dp[i].first == mx) ans = (ans + dp[i].second) % MOD;

    cout << mx << " " << ans;

    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In member function 'pi Seg::update(int, int, int, int, pi)':
trapezoid.cpp:29:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid = s + e >> 1;
      |                   ~~^~~
trapezoid.cpp: In member function 'pi Seg::query(int, int, int, int, int)':
trapezoid.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = s + e >> 1;
      |                   ~~^~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100