Submission #235436

#	Time	Username	Problem	Language	Result	Execution time	Memory
235436		parsa_mobed	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1093 ms	117336 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair <int , int>
#define F first
#define S second
#define Mx first
#define Mn second

const int N = 2e5 + 5, inf = 1e9 + 1;
int a[N], b[N], S[N], p[N], n, k, timer = 0;
pii A[N];

struct Node {
    vector <int> NQ, Suf;
    vector <pii> SQ;
} seg[N<<2];

void NOTQ(int l, int r, int L = 0, int R = n, int id = 1) {
    if (r <= L || R <= l) return ;
    if (l <= L && R <= r) {
        seg[id].NQ.push_back(timer);
        return ;
    }
    int mid = (L+R)>>1;
    NOTQ(l, r, L, mid, id<<1);
    NOTQ(l, r, mid, R, id<<1|1);
}
void SETQ(int l, int r, int val, int L = 0, int R = n, int id = 1) {
    if (r <= L || R <= l) return ;
    if (l <= L && R <= r) {
        seg[id].SQ.push_back({val, timer});
        return ;
    }
    int mid = (L+R)>>1;
    SETQ(l, r, val, L, mid, id<<1);
    SETQ(l, r, val, mid, R, id<<1|1);
}
int GET(int l, int L = 0, int R = n, int id = 1) {
    int t = 0;
    if (seg[id].SQ.size()) {
        int x = lower_bound(all(seg[id].SQ), make_pair(A[l].Mn, 0)) - seg[id].SQ.begin();
        t = seg[id].Suf[x];
    }
    if (R - L == 1) return t;
    int mid = (L+R)>>1;
    if (l < mid) return max(t, GET(l, L, mid, id<<1));
    else return max(t, GET(l, mid, R, id<<1|1));
}
int GET2(int l, int t, int L = 0, int R = n, int id = 1) {
    int r = 0;
    if (seg[id].NQ.size()) {
        int x = lower_bound(all(seg[id].NQ), t) - seg[id].NQ.begin();
        r = seg[id].NQ.size() - x;
    }
    if (R - L == 1) return r;
    int mid = (L+R)>>1;
    if (l < mid) return r + GET2(l, t, L, mid, id<<1);
    else return r + GET2(l, t, mid, R, id<<1|1);
}

void FixEverything(int L = 0, int R = n, int id = 1) {
    sort(all(seg[id].SQ)), sort(all(seg[id].NQ));
    seg[id].Suf.resize(seg[id].SQ.size() + 1);
    for (int i = seg[id].SQ.size() - 1; i >= 0; i--) seg[id].Suf[i] = max(seg[id].Suf[i+1], seg[id].SQ[i].S);
    if (R - L == 1) return ;
    int mid = (L+R)>>1;
    FixEverything(L, mid, id<<1);
    FixEverything(mid, R, id<<1|1);
}

bool cmp(int i, int j) {return A[i] < A[j];}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        A[i].Mn = a[i], A[i].Mx = b[i], p[i] = i;
        if (A[i].Mn > A[i].Mx) swap(A[i].Mn, A[i].Mx), S[i] = 1;
    }
    sort(p, p + n, cmp), sort(A, A + n);
    for (int i = 0; i < n; i++) if (S[p[i]] == 1) SETQ(i, i + 1, inf);
    for (timer++; timer <= k; timer++) {
        int t; cin >> t;
        int x = upper_bound(A, A + n, make_pair(t, inf)) - A;
        NOTQ(0, x), SETQ(x, n, t);
    }
    FixEverything();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int t = GET(i);
        int x = GET2(i, t)&1;
        if (t != 0) S[p[i]] = 1;
        if ((S[p[i]]^x) == 1) ans += A[i].Mx;
        else ans += A[i].Mn;
    }
    cout << ans << "\n";


    return 0;
}

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