oj.uz

답안 #506228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
506228 2022-01-11T22:55:14 Z colossal_pepe 운세 보기 2 (JOI14_fortune_telling2) C++17
4 / 100
 3000 ms 844 KB 
#include <algorithm>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>
using namespace std;
using namespace __gnu_pbds;

#define pow2(p) (1 << (p))

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

int n, k;
vector<int> a, b, t, flips;

void makePancakes() {
    vector<int> t_sorted = t;
    sort(t_sorted.begin(), t_sorted.end());
    for (int i = 0; i < n; i++) {
        flips[i] +=
            t_sorted.end() -
            lower_bound(t_sorted.begin(), t_sorted.end(), max(a[i], b[i]));
    }
}

void adjustFlips() {
    /*vector<pair<int, int>> tp(k);
    for (int i = 0; i < k; i++) {
        tp[i].first = t[i];
        tp[i].second = i;
    }
    sort(tp.begin(), tp.end());
    int st[k][20];
    memset(st, 0, sizeof(st));
    for (int i = 0; i < k; i++) {
        st[i][0] = tp[i].second;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i + pow2(j) - 1 < k; i++) {
            st[i][j] = max(st[i][j - 1], st[i + pow2(j - 1)][j]);
        }
    }
    int log2[200005];
    log2[1] = 0;
    for (int i = 2; i < 200005; i++) {
        log2[i] = log2[i / 2] + 1;
    }*/
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) {
        p[i].second = i;
        /*int l =
            lower_bound(tp.begin(), tp.end(), make_pair(min(a[i], b[i]), -1)) -
        tp.begin(); int r = lower_bound(tp.begin(), tp.end(),
        make_pair(max(a[i], b[i]), -1)) - tp.begin(); if (l == r) { p[i].first =
        -1; continue;
        }
        flips[i] += (b[i] > a[i]);
        int len = r - l, j = log2[r - l];
        p[i].first = max(st[l][j], st[l + len - pow2(j)][j]);*/
        p[i].first = -1;
        for (int j = 0; j < k; j++) {
            if (min(a[i], b[i]) <= t[j] and t[j] < max(a[i], b[i]))
                p[i].first = j;
        }
    }
    sort(p.begin(), p.end());
    /*int ti = 0, pi = 0;
    ordered_set os;
    while (ti < k) {
        os.insert({t[ti], ti});
        while (pi < n and p[pi].first == ti) {
            flips[p[pi].second] -= os.size() -
    os.order_of_key({max(a[p[pi].second], b[p[pi].second]), -1}); pi++;
        }
        ti++;
    }*/
    for (auto [c, i] : p) {
        if (c != -1) flips[i] += (b[i] > a[i]);
        for (int j = 0; j < c; j++) {
            if (max(a[i], b[i]) <= t[j]) flips[i]--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    a.resize(n), b.resize(n), flips.resize(n);
    t.resize(k);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
    makePancakes();
    adjustFlips();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (flips[i] % 2)
            ans += b[i];
        else
            ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 332 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 332 KB Output is correct
14 Correct 753 ms 528 KB Output is correct
15 Execution timed out 3036 ms 844 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 332 KB Output is correct
14 Correct 753 ms 528 KB Output is correct
15 Execution timed out 3036 ms 844 KB Time limit exceeded
16 Halted 0 ms 0 KB -