제출 #146043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146043		osaaateiasavtnl	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	24 ms	21752 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, C = 3 * N;
int n, k; int a[N], b[N], t[N], r[C], mx[C << 2];
void build(int v, int tl, int tr) {
    if (tl == tr) { mx[v] = r[tl]; return; }
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -1;
    if (l <= tl && tr <= r) return mx[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
vector <int> c;
int pos(int x) { return lower_bound(c.begin(), c.end(), x) - c.begin(); }
int last[N], d[N];
vector <int> card[N];
int f[C];
void upd(int i) { i = C - i - 1; for (; i < C; i |= i + 1) ++f[i]; }
int get(int i) { i = C - i - 1; int ans = 0; for (; i >= 0; i &= i + 1, --i) ans += f[i]; return ans; }
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> k;
    for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; c.app(a[i]); c.app(b[i]); }
    for (int i = 0; i < k; ++i) { cin >> t[i]; c.app(t[i]); }
    sort(all(c)); c.resize(unique(all(c)) - c.begin());
    for (int i = 0; i < n; ++i) { a[i] = pos(a[i]); b[i] = pos(b[i]); }
    for (int i = 0; i < k; ++i) { t[i] = pos(t[i]); r[t[i]] = i; }
    build(0, 0, C - 1);
    for (int i = 0; i < n; ++i) {
        last[i] = get(0, 0, C - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);
        card[last[i] + 1].app(i);
    }
    for (int i = k - 1; i >= 0; --i) {
        upd(t[i]);
        for (int c : card[i]) {
            d[c] = get(max(a[c], b[c]));
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] < b[i] && last[i] == -1) ++d[i];
        if (d[i] & 1) { ans += c[min(a[i], b[i])]; }
        else { ans += c[max(a[i], b[i])]; }
    }
    cout << ans << '\n';
}   

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