oj.uz

Submission #44707

# Submission time Handle Problem Language Result Execution time Memory
44707 2018-04-05T10:09:06 Z choikiwon Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 300 ms 122644 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;

int N, K;
struct Query {
    int a, b, id;
    bool operator <(const Query &i) const {
        return max(a, b) < max(i.a, i.b);
    }
};
Query query[MN];
int T[MN], ans[MN];
vector<pii> ord;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * K);
        build(0, K - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = T[l];
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int kquer(int k, int l, int r, int n) {
        if(tree[n] < k) return -1;
        if(l == r) return l;
        int m = (l + r)>>1;
        if(tree[2*n + 1] >= k) return kquer(k, m + 1, r, 2*n + 1);
        else return kquer(k, l, m, 2*n);
    }
} bit;

struct Fenwick {
    vector<int> tree;
    void init() {
        tree = vector<int>(K + 1, 0);
    }
    void upd(int idx, int val) {
        for(int i = idx + 1; i <= K; i += (i & -i)) tree[i] += val;
    }
    int quer(int a) {
        int ret = 0;
        for(int i = a + 1; i >= 1; i -= (i & -i)) ret += tree[i];
        return ret;
    }
    int quer(int a, int b) {
        return quer(b) - quer(a - 1);
    }
} fwt;

int main() {
    scanf("%d %d", &N, &K);

    for(int i = 0; i < N; i++) {
        int a, b; scanf("%d %d", &a, &b);
        query[i] = {a, b, i};
    }
    for(int i = 0; i < K; i++) {
        scanf("%d", &T[i]);
    }
    for(int i = 0; i < K; i++) ord.push_back({ T[i], i });

    sort(query, query + N);
    sort(ord.begin(), ord.end());
    bit.init();
    fwt.init();

    ll ans = 0;
    int pos = K - 1;
    for(int i = N - 1; i >= 0; i--) {
        while(pos >= 0 && ord[pos].first >= max(query[i].a, query[i].b)) {
            fwt.upd(ord[pos].second, 1);
            bit.upd(ord[pos].second, -1, 0, K - 1, 1);
            pos--;
        }

        int a = min(query[i].a, query[i].b);
        int t = bit.kquer(a, 0, K - 1, 1);
        int d = fwt.quer(t + 1, K - 1);

        if(t == -1) {
            if(d & 1) ans += query[i].b;
            else ans += query[i].a;
        }
        else {
            if(d & 1) ans += min(query[i].a, query[i].b);
            else ans += max(query[i].a, query[i].b);
        }
    }

    printf("%lld", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:78:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &T[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 764 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 3 ms 1004 KB Output is correct
8 Correct 3 ms 1004 KB Output is correct
9 Correct 2 ms 1004 KB Output is correct
10 Correct 2 ms 1072 KB Output is correct
11 Correct 3 ms 1152 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct
13 Correct 3 ms 1152 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1920 KB Output is correct
2 Correct 23 ms 2848 KB Output is correct
3 Correct 34 ms 4192 KB Output is correct
4 Correct 50 ms 5704 KB Output is correct
5 Correct 46 ms 6864 KB Output is correct
6 Correct 42 ms 8096 KB Output is correct
7 Correct 49 ms 9188 KB Output is correct
8 Correct 41 ms 10348 KB Output is correct
9 Correct 31 ms 11036 KB Output is correct
10 Correct 33 ms 11792 KB Output is correct
11 Correct 35 ms 12468 KB Output is correct
12 Correct 28 ms 13160 KB Output is correct
13 Correct 53 ms 14220 KB Output is correct
14 Correct 43 ms 15308 KB Output is correct
15 Correct 45 ms 16472 KB Output is correct
16 Correct 48 ms 17736 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 24676 KB Output is correct
2 Correct 187 ms 28064 KB Output is correct
3 Correct 256 ms 32436 KB Output is correct
4 Correct 256 ms 39536 KB Output is correct
5 Correct 93 ms 39536 KB Output is correct
6 Correct 300 ms 47144 KB Output is correct
7 Correct 249 ms 52940 KB Output is correct
8 Correct 272 ms 59020 KB Output is correct
9 Correct 225 ms 64576 KB Output is correct
10 Correct 241 ms 70368 KB Output is correct
11 Correct 185 ms 76064 KB Output is correct
12 Correct 250 ms 81824 KB Output is correct
13 Correct 249 ms 87768 KB Output is correct
14 Correct 142 ms 92896 KB Output is correct
15 Correct 143 ms 98008 KB Output is correct
16 Correct 149 ms 103216 KB Output is correct
17 Correct 185 ms 107048 KB Output is correct
18 Correct 216 ms 110808 KB Output is correct
19 Correct 237 ms 116780 KB Output is correct
20 Correct 234 ms 122644 KB Output is correct