Submission #1174141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174141		chikien2009	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	485 ms	46904 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
private:
    int tree_size;
    vector<vector<int>> tree;
    vector<int> base;

    inline void Build(int ind, int l, int r)
    {
        if (l == r)
        {
            tree[ind] = {base[l]};
            return;
        }
        int m = (l + r) >> 1;
        Build(ind << 1, l, m);
        Build(ind << 1 | 1, m + 1, r);
        tree[ind].resize(r - l + 1);
        merge(tree[ind << 1].begin(), tree[ind << 1].end(),
              tree[ind << 1 | 1].begin(), tree[ind << 1 | 1].end(),
              tree[ind].begin());
    }
    inline pair<int, int> Get(int ind, int l, int r, int x, int y)
    {
        int a = lower_bound(tree[ind].begin(), tree[ind].end(), x) - tree[ind].begin();
        int b = lower_bound(tree[ind].begin(), tree[ind].end(), y) - tree[ind].begin();
        if (a == b)
        {
            return {0, tree[ind].size() - b};
        }
        if (l == r)
        {
            return {1, 0};
        }
        int m = (l + r) >> 1;
        pair<int, int> rt = Get(ind << 1 | 1, m + 1, r, x, y);
        if (rt.first)
        {
            return rt;
        }
        pair<int, int> lt = Get(ind << 1, l, m, x, y);
        return make_pair(lt.first, lt.second ^ rt.second);
    }

public:
    inline void Init(vector<int> inp)
    {
        base = inp;
        tree_size = inp.size();
        tree.clear();
        tree.resize(tree_size << 2);
        base.insert(base.begin(), 0);
        Build(1, 1, tree_size);
    }
    inline pair<int, int> Get(int x, int y)
    {
        return Get(1, 1, tree_size, x, y);
    }
} st;

int n, k, a[200000], b[200000];
vector<int> t;
pair<int, int> r;
long long res = 0;

int main()
{
    setup();

    cin >> n >> k;
    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];
    }
    st.Init(t);
    r = st.Get(1, 9);
    for (int i = 0; i < n; ++i)
    {
        r = st.Get(min(a[i], b[i]), max(a[i], b[i]));
        if (r.first && a[i] < b[i])
        {
            swap(a[i], b[i]);
        }
        res += (r.second & 1 ? b[i] : a[i]);
    }
    cout << res;
    return 0;
}

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