Submission #44707

#	Time	Username	Problem	Language	Result	Execution time	Memory
44707		choikiwon	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	300 ms	122644 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65