Submission #62221

#	Time	Username	Problem	Language	Result	Execution time	Memory
62221		Osama_Alkhodairy	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	8 ms	3576 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define finish(x) return cout << x << endl, 0;

struct wavelet {
    int lo, mid, hi;
    vector<int> b;
    wavelet *l = 0, *r = 0;
    wavelet(int x, int y) {
        lo = x, hi = y, mid = x + (y - x) / 2;
    }
    wavelet(vector<int> &a, int x, int y) {
        lo = x, hi = y, mid = x + (y - x) / 2;
        for (auto &i : a) push_back(i);
    }
    // insert a value at the back
    void push_back(int v) {
        if (v < lo || v > hi || lo == hi) return;
        if (!b.size()) {
            b.push_back(0);
            l = new wavelet(lo, mid);
            r = new wavelet(mid + 1, hi);
        }
        if (v <= mid) {
            b.push_back(b.back() + 1);
            this->l->push_back(v);
        }
        else {
            b.push_back(b.back());
            this->r->push_back(v);
        }
    }
    // erase the value at the back
    // returns true if the wavelet node should be deleted
    bool pop_back() {
        if (lo == hi) return false;
        if (b[b.size() - 2] < b[b.size() - 1]) {
            if (this->l->pop_back()) delete l;
        }
        else if (this->r->pop_back()) delete r;
        b.pop_back();
        return b.size() == 1;
    }
    // incoming random operations?:

    // counts the amount of integers (<= x) in the subarray [l, r].
    int celt(int l, int r, int x) {
        if (l > r || lo > x) return 0;
        if (hi <= x) return r - l + 1;
        return this->l->celt(b[l - 1] + 1, b[r], x) + this->r->celt(l - b[l - 1], r - b[r], x);
    }
    // returns the k_th minimal value in the subarray [l, r].
    int kth(int l, int r, int k) {
        if (lo == hi) return lo;
        if (b[r] - b[l - 1] >= k)
            return this->l->kth(b[l - 1] + 1, b[r], k);
        return this->r->kth(l - b[l - 1], r - b[r], k - (b[r] - b[l - 1]));
    }
};

int n, k, x, y;
vector <int> a, b, t;
wavelet w(0, 1e9);

int larger(int l, int r, int x){
    return r - l + 1 - w.celt(l, r, x - 1);
}
int smaller(int l, int r, int x){
    return w.celt(l, r, x);
}
int solve(int a, int b){
    if(larger(0, k - 1, b) + smaller(0, k - 1, a) == n){
        int val = larger(0, k - 1, b);
        if(val % 2) return b;
        return a;
    }
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(larger(mid, k - 1, b) + smaller(mid, k - 1, a) == k - mid) r = mid - 1;
        else l = mid + 1;
    }
    if(b < a) swap(a, b);
    int val = larger(l - 1, k - 1, b);
    if(val % 2) return b;
    return a;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for(int i = 0 ; i < n && cin >> x >> y ; i++)
        a.push_back(x), b.push_back(y);
    for(int i = 0 ; i < k && cin >> x ; i++)
        w.push_back(x);
    ll ans = 0;
    for(int i = 0 ; i < n ; i++)
        ans += solve(a[i], b[i]);
    cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65