Submission #1305761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305761		lsjo	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	842 ms	96908 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long

// coordinate compression + segtree
// segtree stores number of occurrences of index and latest appearance

struct Node {
    int val;
    int summ;
    int maxx;

    Node operator+(Node other) {
        return {val, summ+other.summ, max(maxx, other.maxx)};
    }
};

vector<Node> segtree;

void make_tree(int n) {
    int s = 1;
    while (s <= 2*n) s*=2;
    segtree.resize(s, {0,0,0});
}

void update_tree(Node node, int ind) {
    ind += segtree.size()/2;
    segtree[ind]=node;
    while (ind/=2) segtree[ind]=segtree[ind*2]+segtree[ind*2+1];
}

Node query_tree(int l, int r) {
    vector<pair<int,pair<int,int>>> to_visit;
    to_visit.push_back({1, {0, segtree.size()/2-1}});
    Node t = {0,0,0};
    if (l > r) return t;
    
    while (! to_visit.empty()) {
        auto node = to_visit.back();
        to_visit.pop_back();

        if (l <= node.second.first && node.second.second <= r) {
            t = t + segtree[node.first];
            continue;
        }

        int mid = (node.second.first+node.second.second)/2;
        if (l <= mid) to_visit.push_back({node.first*2, {node.second.first, mid}});
        if (r > mid) to_visit.push_back({node.first*2+1, {mid+1, node.second.second}});
    }

    return t;
}

int a[200005], b[200005], nums[200005];
int latest[200005];
unordered_map<int,int> compress;

signed main() {
    int n, k; cin >> n >> k;
    make_tree(2*n+k+1);

    vector<pair<int,int>> allnums;

    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        allnums.push_back({a[i], 2*i-1});
        allnums.push_back({b[i], 2*i});
        latest[i]=-1;
    }

    for (int i = 1; i <= k; i++) {
        cin >> nums[i];
        allnums.push_back({nums[i], 2*n+i});
    }

    sort(allnums.begin(), allnums.end());
    for (int i = 0; i < allnums.size(); i++) {
        if (!compress.count(allnums[i].first)) compress[allnums[i].first]=i+1;
    }

    for (int i = 1; i <= k; i++) {
        int val=compress[nums[i]];
        Node node = segtree[val+segtree.size()/2];
        node.maxx=i;
        update_tree(node, val);
    }

    // find the final occurrence of the thing
    // and then do a sweepline thing where you update backwards
    // and if the thing

    vector<pair<int,int>> counts;
    vector<int> finals;

    int total=0;

    for (int i = 1; i <= n; i++) {
        Node last = query_tree(compress[min(a[i],b[i])],compress[max(a[i], b[i])]-1);
        if (last.maxx != 0) {
            //cout << i << " last max flipped at " << last.maxx << "\n";
            counts.push_back({last.maxx, i});
        }
        else {
            //cout << i << " never max flipped\n";
            finals.push_back(i);
        }
    }

    sort(counts.begin(), counts.end());
    reverse(counts.begin(), counts.end());

    int ind=k;

    //cout << "counts\n";

    for (auto x : counts) {
        while (ind > x.first) {
            Node last = query_tree(compress[nums[ind]], compress[nums[ind]]);
            last.summ += 1;
            update_tree(last, compress[nums[ind]]);
            ind--;
        }

        Node numflips = query_tree(compress[max(a[x.second],b[x.second])], 2*n+k); // find the number of flips (max(a[i],b[i]) to 2*n+k)
        //cout << "card " << x.second << " swap flipped " << numflips.summ << " times\n";
        if (numflips.summ % 2 == 0) {
            total += max(a[x.second], b[x.second]);
            //cout << "adding " << max(a[x.second], b[x.second]) << "\n";
        }
        else {
            total += min(a[x.second], b[x.second]);
            //cout << "adding " << min(a[x.second], b[x.second]) << "\n";
        }
    }

    while (ind > 0) {
        Node last = query_tree(compress[nums[ind]], compress[nums[ind]]);
        last.summ += 1;
        update_tree(last, compress[nums[ind]]);
        ind--;
    }

    //cout << "finals\n";

    for (auto x : finals) {
        Node numflips = query_tree(compress[min(a[x], b[x])], 2*n+k);
        //cout << "card " << x << " swapped " << numflips.summ << " times\n";
        if (numflips.summ % 2 == 0) {
            //cout << "card " << x << " adding " << a[x] << "\n";
            total += a[x];
        }
        else {
            //cout << "card " << x << " adding " << b[x] << "\n";
            total += b[x];
        }
    }

    cout << total << "\n";
    return 0;

}

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