Submission #391652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
391652	2021-04-19T13:08:31 Z	egod1537	trapezoid (balkan11_trapezoid)	C++14	100 / 100	273 ms	35448 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	3 ms	600 KB	Output is correct
5	Correct	4 ms	972 KB	Output is correct
6	Correct	6 ms	1356 KB	Output is correct
7	Correct	7 ms	1484 KB	Output is correct
8	Correct	12 ms	1996 KB	Output is correct
9	Correct	21 ms	4040 KB	Output is correct
10	Correct	36 ms	6200 KB	Output is correct
11	Correct	60 ms	9276 KB	Output is correct
12	Correct	132 ms	18544 KB	Output is correct
13	Correct	154 ms	21424 KB	Output is correct
14	Correct	225 ms	29100 KB	Output is correct
15	Correct	191 ms	25136 KB	Output is correct
16	Correct	218 ms	26704 KB	Output is correct
17	Correct	273 ms	32088 KB	Output is correct
18	Correct	174 ms	26484 KB	Output is correct
19	Correct	250 ms	34248 KB	Output is correct
20	Correct	266 ms	35448 KB	Output is correct