Submission #246922

#	Time	Username	Problem	Language	Result	Execution time	Memory
246922		receed	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	318 ms	22000 KiB

fortune_telling2

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 18;
int a[N], b[N], t[N], tr[N * 2], f[N];
vector<pair<int, int>> lq[N];

int getm(int cl, int cr, int v=1, int l=0, int r=N) {
    if (cr <= l || r <= cl)
        return -1;
    if (cl <= l && r <= cr)
        return tr[v];
    return max(getm(cl, cr, v * 2, l, (l + r) / 2), getm(cl, cr, v * 2 + 1, (l + r) / 2, r));
}

void add(int p) {
    for (int i = p; i < N; i |= (i + 1))
        f[i]++;
}

int sum(int p) {
    int s = 0;
    for (int i = p; i; i &= (i - 1))
        s += f[i - 1];
    return s;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> li;
    rep(i, n) {
        cin >> a[i] >> b[i];
        li.push_back(a[i]);
        li.push_back(b[i]);
    }
    sort(all(li));
    li.resize(unique(all(li)) - li.begin());
    rep(i, n) {
        a[i] = lower_bound(all(li), a[i]) - li.begin();
        b[i] = lower_bound(all(li), b[i]) - li.begin();
    }
    rep(i, N)
        tr[N + i] = -1;
    rep(i, k) {
        cin >> t[i];
        t[i] = lower_bound(all(li), t[i] + 1) - li.begin();
        tr[N + t[i]] = max(tr[N + t[i]], i);
    }
    for  (int i = N - 1; i > 0; i--)
        tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
    rep(i, n) {
        int lp = getm(min(a[i], b[i]) + 1, max(a[i], b[i]) + 1);
        lq[lp + 1].push_back({max(a[i], b[i]), i});
    }
    ll ans = 0, ca;
    for (int i = k - 1; i >= 0; i--) {
        for (auto &pp : lq[i + 1]) {
            ca = (k - i - 1 - sum(pp.first + 1)) % 2;
            if ((a[pp.second] > b[pp.second]) ^ ca)
                ans += li[a[pp.second]];
            else
                ans += li[b[pp.second]];
        }
        add(t[i]);
    }
    for (auto &pp : lq[0]) {
        ca = (k - sum(pp.first + 1)) % 2;
        if (ca)
            ans += li[b[pp.second]];
        else
            ans += li[a[pp.second]];
    }
    cout << ans;
}

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