Submission #425590

#	Time	Username	Problem	Language	Result	Execution time	Memory
425590		kostia244	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	408 ms	15636 KiB

fortune_telling2

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct MNode { int a = -1; 
    MNode() {}
    MNode(int x) : a(x) {}
    friend MNode operator+(const MNode &a, const MNode &b) {
        return MNode(max(a.a, b.a));
    }
};
struct PNode { int a = 0;
    PNode() {}
    PNode(int x) : a(x) {}
    friend PNode operator+(const PNode &a, const PNode &b) {
        return PNode(a.a^b.a);
    }
};
template<class Node>
struct SegTree {
    int n;
    vector<Node> tree;
    SegTree(int N) : n(N), tree(2*n) {}
    void upd(int pos, Node val) {
        for(tree[pos+=n]=val;pos/=2;)
            tree[pos] = tree[2*pos]+tree[2*pos+1];
    }
    Node query(int l, int r) {
        Node res;
        for(l += n, r += n; l < r; l>>=1,r>>=1) {
            if(l&1) res = res + tree[l++];
            if(r&1) res = tree[--r] + res;
        }
        return res;
    }
};
int n, k;
vector<array<int, 2>> f, ops_sorted;
vector<int> ops, start;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    f.resize(n);
    start.resize(n);
    for(auto &[a, b] : f) cin >> a >> b;
    ops.resize(k);
    for(auto &i : ops) cin >> i;
    for(int i = 0; i < k; i++) ops_sorted.push_back({ops[i], i});
    for(int i = 0; i < n; i++) ops_sorted.push_back({max(f[i][0], f[i][1])-1, i|(1<<30)});
    sort(all(ops_sorted));
    SegTree<MNode> ms(k);
    for(auto [v, i] : ops_sorted) {
        if(i&(1<<30)) {
            i -= 1<<30;
            int pos = k;
            for(int z = 1<<18; z>>=1;)
                if(pos-z>=0 && ms.query(pos-z, k).a < min(f[i][0], f[i][1]))
                    pos -= z;
            start[i] = pos;
        } else {
            ms.upd(i, MNode(v));
        }
    }
    SegTree<PNode> xr(k);
    ops_sorted.clear();
    for(int i = 0; i < k; i++) ops_sorted.push_back({ops[i], i});
    for(int i = 0; i < n; i++) ops_sorted.push_back({max(f[i][0], f[i][1]), i-(1<<30)});
    sort(all(ops_sorted), greater<>());
    ll sum = 0;
    for(auto [v, i] : ops_sorted) {
        if(i<0) {
            i+=1<<30;
            if(start[i] && f[i][0] < f[i][1]) swap(f[i][0], f[i][1]);
            if(xr.query(start[i], k).a)
                swap(f[i][0], f[i][1]);
            sum += f[i][0];
        } else {
            xr.upd(i, PNode(1));
        }
    }
    cout << sum << '\n';
}

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