Submission #554553

#	Time	Username	Problem	Language	Result	Execution time	Memory
554553		AA_Surely	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	267 ms	14984 KiB

fortune_telling2

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

struct Card {
    int a, b, id;
    bool ch = 0;

    inline bool operator < (const Card other) {
        return a < other.a;
    }
} ns[N];

int n, k;
int stree[N << 2], mtree[N << 2];
PII ks[N];

#define lc now << 1
#define rc now << 1 | 1 

void mchange(int id, int val, int now = 1, int ls = 0, int rs = k - 1) {
    if (ls == rs) {
        mtree[now] = val;
        return;
    }

    int mid = (ls + rs) >> 1;
    if (id <= mid) mchange(id, val, lc, ls, mid);
    else mchange(id, val, rc, mid + 1, rs);
    
    mtree[now] = min(mtree[lc], mtree[rc]);
    return;
}

int descend(int val, int now = 1, int ls = 0, int rs = k - 1) {
    if (mtree[now] >= val) return INF;
    if (ls == rs) return ls;
    int mid = (ls + rs) >> 1;
    int case1 = descend(val, rc, mid + 1, rs);
    return (case1 == INF ? descend(val, lc, ls, mid) : case1);
}

int sbuild(int now = 1, int ls = 0, int rs = k - 1) {
    if (ls == rs) return stree[now] = 1;
    int mid = (ls + rs) >> 1;
    return stree[now] = sbuild(lc, ls, mid) + sbuild(rc, mid + 1, rs);
}

int get(int lq, int rq, int now = 1, int ls = 0, int rs = k - 1) {
    if (rq < lq || rq < ls || rs < lq) return 0;
    if (lq <= ls && rs <= rq) return stree[now];
    int mid = (ls + rs) >> 1;
    return get(lq, rq, lc, ls, mid) + get(lq, rq, rc, mid + 1, rs);
}

void schange(int id, int val, int now = 1, int ls = 0, int rs = k - 1) {
    if (ls == rs) {
        stree[now] = val;
        return;
    }

    int mid = (ls + rs) >> 1;
    if (id <= mid) schange(id, val, lc, ls, mid);
    else schange(id, val, rc, mid + 1, rs);

    stree[now] = stree[lc] + stree[rc];
    return;
}

int main() {
    IOS;
    
    cin >> n >> k;
    F0R(i, n) {
        cin >> ns[i].a >> ns[i].b;
        if (ns[i].a > ns[i].b) {
            swap(ns[i].a, ns[i].b);
            ns[i].ch = 1;
        }
    }

    F0R(i, k) {
        cin >> ks[i].F;
        ks[i].S = i;
    }

    F0R(i, k) mchange(i, ks[i].F);
    sbuild();

    sort(ks, ks + k);
    sort(ns, ns + n);

    /*cout << "descend(9) = " << descend(9) << endl;
    cout << "get(2, 2) = " << get(2, 2) << endl;

    F0R(i, n) {
        cout << ns[i].a << ' ' << ns[i].b << " - " << endl;
    }*/
    
    int ptr = 0;
    LL ans = 0;
    F0R(i, n) {
        while(ptr < k && ks[ptr].F < ns[i].a) {
            mchange(ks[ptr].S, INF);
            schange(ks[ptr].S, 0);
            ptr++;
        }

        int pl = descend(ns[i].b);
        if (pl == INF) {
            int sum = get(0, k - 1);
            if ((sum & 1) ^ (ns[i].ch)) ans += ns[i].b;
            else ans += ns[i].a;
            continue;
        }

        int sum = get(pl + 1, k - 1);
        if (sum & 1) ans += ns[i].a;
        else ans += ns[i].b;

        //cout << "for card " << ns[i].a << ' ' << ns[i].b << " added : " << (sum & 1 ? ns[i].a : ns[i].b) << endl;
    }

    cout << ans;
}

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