oj.uz

Submission #234277

# Submission time Handle Problem Language Result Execution time Memory
234277 2020-05-23T17:47:46 Z DS007 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 748 ms 73748 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5;
vector<int> t[N * 4];
int n, k, a[N], b[N], c[N];

void build(int v, int l, int r) {
    if (l == r) {
        t[v].push_back(c[l]);
        return;
    }

    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), back_inserter(t[v]));
}

int last(int v, int l, int r, int tl, int tr) {
    if (l == r) {
        if (tl <= c[l] && c[l] <= tr)
            return l;
        else
            return -1;
    }

    int mid = (l + r) / 2;
    if (lower_bound(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), tl) == upper_bound(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), tr))
        return last(v * 2, l, mid, tl, tr);
    else
        return last(v * 2 + 1, mid + 1, r, tl, tr);
}

int count(int v, int l, int r, int tl, int tr, int lower) {
    if (tl > tr)
        return 0;
    else if (l == tl && r == tr)
        return t[v].end() - lower_bound(t[v].begin(), t[v].end(), lower);

    int mid = (l + r) / 2;
    return count(v * 2, l, mid, tl, min(mid, tr), lower) + count(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr, lower);
}

int solveTestCase(int test) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    for (int i = 0; i < k; i++) cin >> c[i];
    build(1, 0, k - 1);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            ans += a[i];
            continue;
        }

        int tl = last(1, 0, k - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);
        int f = count(1, 0, k - 1, tl + 1, k - 1, max(a[i], b[i]));

        if (tl == -1) {
            if (f % 2)
                ans += b[i];
            else
                ans += a[i];
        } else {
            if (f % 2)
                ans += min(a[i], b[i]);
            else
                ans += max(a[i], b[i]);
        }
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message

fortune_telling2.cpp: In function 'long long int solveTestCase(long long int)':
fortune_telling2.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19328 KB Output is correct
2 Correct 17 ms 19328 KB Output is correct
3 Correct 19 ms 19328 KB Output is correct
4 Correct 18 ms 19328 KB Output is correct
5 Correct 17 ms 19200 KB Output is correct
6 Correct 18 ms 19328 KB Output is correct
7 Correct 17 ms 19328 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 17 ms 19328 KB Output is correct
10 Correct 17 ms 19328 KB Output is correct
11 Correct 17 ms 19456 KB Output is correct
12 Correct 17 ms 19328 KB Output is correct
13 Correct 17 ms 19328 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19328 KB Output is correct
2 Correct 17 ms 19328 KB Output is correct
3 Correct 19 ms 19328 KB Output is correct
4 Correct 18 ms 19328 KB Output is correct
5 Correct 17 ms 19200 KB Output is correct
6 Correct 18 ms 19328 KB Output is correct
7 Correct 17 ms 19328 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 17 ms 19328 KB Output is correct
10 Correct 17 ms 19328 KB Output is correct
11 Correct 17 ms 19456 KB Output is correct
12 Correct 17 ms 19328 KB Output is correct
13 Correct 17 ms 19328 KB Output is correct
14 Correct 38 ms 21760 KB Output is correct
15 Correct 68 ms 24624 KB Output is correct
16 Correct 93 ms 26112 KB Output is correct
17 Correct 125 ms 30196 KB Output is correct
18 Correct 123 ms 30324 KB Output is correct
19 Correct 128 ms 30324 KB Output is correct
20 Correct 124 ms 30324 KB Output is correct
21 Correct 104 ms 30324 KB Output is correct
22 Correct 75 ms 29812 KB Output is correct
23 Correct 74 ms 29812 KB Output is correct
24 Correct 81 ms 29796 KB Output is correct
25 Correct 73 ms 29848 KB Output is correct
26 Correct 98 ms 30068 KB Output is correct
27 Correct 133 ms 30324 KB Output is correct
28 Correct 95 ms 30324 KB Output is correct
29 Correct 136 ms 30220 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19328 KB Output is correct
2 Correct 17 ms 19328 KB Output is correct
3 Correct 19 ms 19328 KB Output is correct
4 Correct 18 ms 19328 KB Output is correct
5 Correct 17 ms 19200 KB Output is correct
6 Correct 18 ms 19328 KB Output is correct
7 Correct 17 ms 19328 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 17 ms 19328 KB Output is correct
10 Correct 17 ms 19328 KB Output is correct
11 Correct 17 ms 19456 KB Output is correct
12 Correct 17 ms 19328 KB Output is correct
13 Correct 17 ms 19328 KB Output is correct
14 Correct 38 ms 21760 KB Output is correct
15 Correct 68 ms 24624 KB Output is correct
16 Correct 93 ms 26112 KB Output is correct
17 Correct 125 ms 30196 KB Output is correct
18 Correct 123 ms 30324 KB Output is correct
19 Correct 128 ms 30324 KB Output is correct
20 Correct 124 ms 30324 KB Output is correct
21 Correct 104 ms 30324 KB Output is correct
22 Correct 75 ms 29812 KB Output is correct
23 Correct 74 ms 29812 KB Output is correct
24 Correct 81 ms 29796 KB Output is correct
25 Correct 73 ms 29848 KB Output is correct
26 Correct 98 ms 30068 KB Output is correct
27 Correct 133 ms 30324 KB Output is correct
28 Correct 95 ms 30324 KB Output is correct
29 Correct 136 ms 30220 KB Output is correct
30 Correct 198 ms 67044 KB Output is correct
31 Correct 319 ms 68464 KB Output is correct
32 Correct 452 ms 70124 KB Output is correct
33 Correct 696 ms 73708 KB Output is correct
34 Correct 184 ms 66668 KB Output is correct
35 Correct 723 ms 73708 KB Output is correct
36 Correct 702 ms 73708 KB Output is correct
37 Correct 706 ms 73708 KB Output is correct
38 Correct 695 ms 73708 KB Output is correct
39 Correct 734 ms 73708 KB Output is correct
40 Correct 547 ms 73580 KB Output is correct
41 Correct 748 ms 73724 KB Output is correct
42 Correct 726 ms 73616 KB Output is correct
43 Correct 332 ms 72940 KB Output is correct
44 Correct 319 ms 72940 KB Output is correct
45 Correct 324 ms 73108 KB Output is correct
46 Correct 392 ms 71788 KB Output is correct
47 Correct 396 ms 71660 KB Output is correct
48 Correct 614 ms 73748 KB Output is correct
49 Correct 543 ms 73708 KB Output is correct