Submission #506241

#	Time	Username	Problem	Language	Result	Execution time	Memory
506241		colossal_pepe	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	409 ms	35864 KiB

fortune_telling2

#include <algorithm>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>
using namespace std;
using namespace __gnu_pbds;
 
#define pow2(p) (1 << (p))
 
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
 
int n, k;
vector<int> a, b, t, flips;
 
void makePancakes() {
    vector<int> t_sorted = t;
    sort(t_sorted.begin(), t_sorted.end());
    for (int i = 0; i < n; i++) {
        flips[i] +=
            t_sorted.end() -
            lower_bound(t_sorted.begin(), t_sorted.end(), max(a[i], b[i]));
    }
}
 
void adjustFlips() {
    vector<pair<int, int>> tp(k);
    for (int i = 0; i < k; i++) {
        tp[i].first = t[i];
        tp[i].second = i;
    }
    sort(tp.begin(), tp.end());
    int st[k][20];
    memset(st, 0, sizeof(st));
    for (int i = 0; i < k; i++) {
        st[i][0] = tp[i].second;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i + pow2(j) - 1 < k; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
    int log2[200005];
    log2[1] = 0;
    for (int i = 2; i < 200005; i++) {
        log2[i] = log2[i / 2] + 1;
    }
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) {
        p[i].second = i;
        p[i].first = -1;
        int l =
            lower_bound(tp.begin(), tp.end(), make_pair(min(a[i], b[i]), -1)) -
            tp.begin();
        int r =
            lower_bound(tp.begin(), tp.end(), make_pair(max(a[i], b[i]), -1)) -
            tp.begin();
        if (l == r) continue;
        flips[i] += (b[i] > a[i]);
        int j = log2[r - l];
        p[i].first = max(st[l][j], st[r - (1 << j)][j]);
        
    }
    sort(p.begin(), p.end());
    int ti = 0, pi = 0;
    while (p[pi].first == -1) pi++;
    ordered_set os;
    while (ti < k) {
        os.insert({t[ti], ti});
        while (pi < n and p[pi].first == ti) {
            flips[p[pi].second] -=
                os.size() -
                os.order_of_key({max(a[p[pi].second], b[p[pi].second]), -1});
            pi++;
        }
        ti++;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    a.resize(n), b.resize(n), flips.resize(n);
    t.resize(k);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
    makePancakes();
    adjustFlips();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (flips[i] % 2)
            ans += b[i];
        else
            ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

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