Submission #1290645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290645		kreukpg	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	330 ms	69832 KiB

fortune_telling2

// code by phongln
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fo(i, a, b, k) for (ll i = a; i <= b; i += k)
#define fod(i, a, b, k) for (ll i = a; i >= b; i -= k)
#define lop(x, s) for (auto x : s)
#define sz(s) s.size()
#define all(s) s.begin(), s.end()
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define sq(a) (a)*(a)
#define cb(a) (a)*(a)*(a)
#define NAME "TEST"
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

struct card {
    ll a, b;
};

ll n, k;
ll t[maxn];
card a[maxn];

vector<pair<ll, ll>> T;
vector<ll> tree1;
vector<vector<ll>> tree2;

void build1(ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree1[v] = T[tl].se;
    } else {
        ll tm = (tl + tr) >> 1;
        build1(v << 1, tl, tm);
        build1(v << 1 | 1, tm + 1, tr);
        tree1[v] = max(tree1[v << 1], tree1[v << 1 | 1]);
    }
}

ll get1(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return tree1[v];
    ll tm = (tl + tr) >> 1;
    return max(get1(v << 1, tl, tm, l, min(r, tm)),
               get1(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}

void build2(ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree2[v].clear();
        tree2[v].pb(t[tl]);
    } else {
        ll tm = (tl + tr) >> 1;
        build2(v << 1, tl, tm);
        build2(v << 1 | 1, tm + 1, tr);
        tree2[v].clear();
        tree2[v].reserve(tree2[v << 1].size() + tree2[v << 1 | 1].size());
        merge(all(tree2[v << 1]), all(tree2[v << 1 | 1]), back_inserter(tree2[v]));
    }
}

ll get2(ll v, ll tl, ll tr, ll l, ll r, ll val) {
    if (l > r) return 0;
    if (l == tl && r == tr) {
        auto it = lower_bound(all(tree2[v]), val);
        return tree2[v].end() - it;
    }
    ll tm = (tl + tr) >> 1;
    return get2(v << 1, tl, tm, l, min(r, tm), val) +
           get2(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, val);
}

void init() {
}

void solve() {
    cin >> n >> k;
    fo(i, 1, n, 1) cin >> a[i].a >> a[i].b;
    fo(i, 1, k, 1) cin >> t[i];

    if (k > 0) {
        T.resize(k);
        fo(j, 1, k, 1) T[j - 1] = mp(t[j], j);
        sort(all(T));

        tree1.assign(4 * k + 5, 0);
        build1(1, 0, k - 1);

        tree2.assign(4 * (k + 1) + 5, vector<ll>());
        build2(1, 1, k);
    } else {
        T.clear();
        tree1.clear();
        tree2.clear();
    }

    ll res = 0;
    fo(i, 1, n, 1) {
        ll A = a[i].a, B = a[i].b;
        ll va = A, vb = B;
        ll ins = 0;
        if (A > B) swap(va, vb), ins = 1;

        ll mx = 0;
        if (k > 0) {
            auto it1 = lower_bound(all(T), mp(va, -inf));
            auto it2 = lower_bound(all(T), mp(vb, -inf));
            ll ida = it1 - T.begin();
            ll idb = it2 - T.begin();
            if (ida <= idb - 1)
                mx = get1(1, 0, k - 1, ida, idb - 1);
        }

        ll flc = 0;
        ll fs = 0;
        if (mx == 0) {
            if (k > 0) flc = get2(1, 1, k, 1, k, vb);
            fs = ins ^ (flc % 2);
        } else {
            if (mx + 1 <= k) flc = get2(1, 1, k, mx + 1, k, vb);
            fs = 1 ^ (flc % 2);
        }

        res += (fs == 0 ? va : vb);
    }

    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(NAME".INP", "r", stdin);
    // freopen(NAME".OUT", "w", stdout);
    init();
    ll tt = 1;
    while (tt--) solve();
    return 0;
}

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