Submission #47700

#	Time	Username	Problem	Language	Result	Execution time	Memory
47700		qoo2p5	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	245 ms	118616 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = 1 << 18;

int n, k;
int a[N], b[N];
pair<int, int> op[N];

int sum[2 * N], mi[2 * N];

void upd(int i, int v) {
    i += N;
    sum[i] = 1;
    mi[i] = v;
    i /= 2;
    while (i) {
        sum[i] = sum[2 * i] + sum[2 * i + 1];
        mi[i] = min(mi[2 * i], mi[2 * i + 1]);
        i /= 2;
    }
}

int get(int i, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) {
        return 0;
    }
    if (l <= tl && tr <= r) {
        return sum[i];
    }
    int tm = (tl + tr) / 2;
    return get(2 * i, tl, tm, l, r) + get(2 * i + 1, tm, tr, l, r);
}

int find(int i, int tl, int tr, int l, int r, int v) {
    if (tl >= r || tr <= l || mi[i] >= v) {
        return -1;
    }
    if (tl == tr - 1) {
        return tl;
    }
    int tm = (tl + tr) / 2;
    int res = find(2 * i + 1, tm, tr, l, r, v);
    if (res != -1) {
        return res;
    }
    return find(2 * i, tl, tm, l, r, v);
}

void run() {
    cin >> n >> k;
    rep(i, 0, n) {
        cin >> a[i] >> b[i];
    }
    rep(i, 0, k) {
        cin >> op[i].first;
        op[i].second = i;
    }
    sort(op, op + k);
    
    vector<int> p(n);
    rep(i, 0, n) {
        p[i] = i;
    }
    sort(all(p), [] (int i, int j) {
        return min(a[i], b[i]) > min(a[j], b[j]);
    });
    
    int ptr = k - 1;
    rep(i, 0, 2 * N) {
        mi[i] = INF;
    }
    ll ans = 0;
    rep(ii, 0, n) {
        int i = p[ii];
        while (ptr >= 0 && op[ptr].first >= min(a[i], b[i])) {
            upd(op[ptr].second, op[ptr].first);
            ptr--;
        }
        
        int pos = find(1, 0, N, 0, N, max(a[i], b[i]));
        if (pos != -1 && a[i] < b[i]) {
            swap(a[i], b[i]);
        }
        int cnt = get(1, 0, N, pos + 1, N);
        ans += (cnt % 2 ? b[i] : a[i]);
    }
    
    cout << ans << "\n";
}

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