oj.uz

Submission #506231

# Submission time Handle Problem Language Result Execution time Memory
506231 2022-01-11T23:03:09 Z colossal_pepe Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 33228 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;
        p[i].first = -1;
        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) continue;
        flips[i] += (b[i] > a[i]);
        for (int j = l; j < r; j++) {
            p[i].first = max(p[i].first, tp[j].second);
        }
        
    }
    sort(p.begin(), p.end());
    int ti = 0, pi = 0;
    while (p[pi].first == -1) pi++;
    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++;
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 416 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 416 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 47 ms 1892 KB Output is correct
15 Correct 173 ms 3744 KB Output is correct
16 Correct 367 ms 5376 KB Output is correct
17 Correct 611 ms 7164 KB Output is correct
18 Correct 620 ms 8292 KB Output is correct
19 Correct 725 ms 8300 KB Output is correct
20 Correct 134 ms 8356 KB Output is correct
21 Correct 1543 ms 8276 KB Output is correct
22 Correct 880 ms 7828 KB Output is correct
23 Correct 605 ms 7828 KB Output is correct
24 Correct 227 ms 7820 KB Output is correct
25 Correct 1157 ms 7852 KB Output is correct
26 Correct 91 ms 8092 KB Output is correct
27 Correct 54 ms 8352 KB Output is correct
28 Correct 260 ms 8324 KB Output is correct
29 Correct 48 ms 8328 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 416 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 47 ms 1892 KB Output is correct
15 Correct 173 ms 3744 KB Output is correct
16 Correct 367 ms 5376 KB Output is correct
17 Correct 611 ms 7164 KB Output is correct
18 Correct 620 ms 8292 KB Output is correct
19 Correct 725 ms 8300 KB Output is correct
20 Correct 134 ms 8356 KB Output is correct
21 Correct 1543 ms 8276 KB Output is correct
22 Correct 880 ms 7828 KB Output is correct
23 Correct 605 ms 7828 KB Output is correct
24 Correct 227 ms 7820 KB Output is correct
25 Correct 1157 ms 7852 KB Output is correct
26 Correct 91 ms 8092 KB Output is correct
27 Correct 54 ms 8352 KB Output is correct
28 Correct 260 ms 8324 KB Output is correct
29 Correct 48 ms 8328 KB Output is correct
30 Correct 954 ms 33228 KB Output is correct
31 Execution timed out 3014 ms 22184 KB Time limit exceeded
32 Halted 0 ms 0 KB -