oj.uz

답안 #238573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238573 2020-06-11T22:10:37 Z thecodingwizard 사다리꼴 (balkan11_trapezoid) C++11
48 / 100
 500 ms 8292 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ii pair<int, int>
#define f first
#define s second

const int mod = 30013;

int main() {
    int n; cin >> n;
    vector<ii> topLeft;
    vector<pair<ii, ii>> A;
    for (int i = 0; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        A.pb({{a,b},{c,d}});
        topLeft.pb({a,i});
    }
    sort(topLeft.begin(), topLeft.end());

    int tlIdx = 0;
    set<ii> q;
    map<int, ii> traps;
    ii dp[n];
    while (tlIdx != n) {
        while (!q.empty() && q.begin()->f < topLeft[tlIdx].f) {
            int x = q.begin()->s;
            q.erase(q.begin());
            auto it = traps.lower_bound(A[x].s.s);
            while (it != traps.end() && it->s.f <= dp[x].f) {
                if (it->s.f == dp[x].f) {
                    it->s.s = (it->s.s+dp[x].s)%mod;
                    it++;
                } else {
                    it = traps.erase(it);
                }
            }
            it = traps.lower_bound(A[x].s.s);
            int additional = 0;
            if (!traps.empty()) {
                if (it != traps.begin()) {
                    it--;
                    if (it->s.f > dp[x].f) continue;
                    if (it->s.f == dp[x].f) {
                        additional += it->s.s;
                    }
                }
            }
            traps[A[x].s.s] = make_pair(dp[x].f, (additional+dp[x].s)%mod);
        }

        int u = topLeft[tlIdx].s;
        int best = 1, ct = 1;
        if (!traps.empty()) {
            auto it = traps.lower_bound(A[u].s.f);
            if (it != traps.begin()) {
                it--;
                best = 1 + it->s.f;
                ct = it->s.s;
            }
        }
        dp[u] = make_pair(best, ct);
        q.insert({A[u].f.s, u});

        tlIdx++;
    }
    int ans = 0;
    int ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i].f > ans) {
            ans = dp[i].f; ans2 = dp[i].s;
        } else if (dp[i].f == ans) {
            ans2 += dp[i].s;
        }
    }

    cout << ans << " " << ans2 << endl;

    return 0;
}

Subtask #1
48.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Partially correct 5 ms 384 KB Partially correct
4 Partially correct 6 ms 384 KB Partially correct
5 Correct 9 ms 512 KB Output is correct
6 Partially correct 12 ms 512 KB Partially correct
7 Partially correct 12 ms 640 KB Partially correct
8 Partially correct 15 ms 768 KB Partially correct
9 Partially correct 28 ms 1148 KB Partially correct
10 Partially correct 48 ms 1780 KB Partially correct
11 Partially correct 100 ms 2288 KB Partially correct
12 Partially correct 132 ms 3620 KB Partially correct
13 Correct 189 ms 4080 KB Output is correct
14 Partially correct 269 ms 5244 KB Partially correct
15 Partially correct 211 ms 5220 KB Partially correct
16 Partially correct 235 ms 5476 KB Partially correct
17 Partially correct 283 ms 5988 KB Partially correct
18 Partially correct 215 ms 7012 KB Partially correct
19 Execution timed out 958 ms 8292 KB Time limit exceeded
20 Execution timed out 974 ms 8036 KB Time limit exceeded