oj.uz

답안 #391652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391652 2021-04-19T13:08:31 Z egod1537 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 273 ms 35448 KB 
#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

# 결과 실행 시간 메모리 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