Submission #295447

#	Time	Username	Problem	Language	Result	Execution time	Memory
295447		limabeans	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	250 ms	7416 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 2e5+10;
const int inf = 2e9;

int n, k;
vector<array<int,2>> card;
vector<pair<int,int>> flip; // value, index


bool sum[maxn*4];
int tmin[maxn*4];

void build(int v, int tl, int tr) {
    if (tl==tr) {
	tmin[v]=inf;
    } else {
	int tm=(tl+tr)/2;
	build(2*v,tl,tm);
	build(2*v+1,tm+1,tr);
	tmin[v]=min(tmin[2*v],tmin[2*v+1]);
    }
}

void upd(int v, int tl, int tr, int i, int val) {
    if (tl==tr) {
	tmin[v] = val;
	sum[v] = true;
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,val);
	} else {
	    upd(2*v+1,tm+1,tr,i,val);
	}
	tmin[v] = min(tmin[2*v], tmin[2*v+1]);
	sum[v] = sum[2*v] ^ sum[2*v+1];
    }
}


// 0: everything is >= val
// get first index from rhs that is < val
int get(int v, int tl, int tr, int val) {
    if (val <= tmin[v]) {
	return 0;
    }
    if (tl==tr) {
	assert(tmin[v]<val);
	return tl;
    } else {
	int tm=(tl+tr)/2;
	int rhs = get(2*v+1,tm+1,tr,val);
	if (rhs > 0) {
	    return rhs;
	}
	return get(2*v,tl,tm,val);
    }
}

bool qry(int v, int tl, int tr, int l, int r) {
    if (l>r) return false;
    if (l==tl && tr==r) return sum[v];
    int tm=(tl+tr)/2;
    return qry(2*v,tl,tm,l,min(r,tm)) ^ qry(2*v+1,tm+1,tr,max(tm+1,l),r);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    card.resize(n);
    for (int i=0; i<n; i++) {
	cin>>card[i][0]>>card[i][1];
    }
    flip.resize(k);
    for (int i=1; i<=k; i++) {
	cin>>flip[i-1].first;
	flip[i-1].second=i;
    }


    sort(flip.rbegin(),flip.rend());

    sort(card.begin(), card.end(), [&](array<int,2> c1, array<int,2> c2) {
	    return min(c1[0],c1[1]) > min(c2[0],c2[1]);
	});


    build(1,1,k);


    ll res = 0;
    int j=0;
    for (auto ca: card) {
	int lo = min(ca[0], ca[1]);
	int hi = max(ca[0], ca[1]);

	bool flag = false;
	if (lo == ca[0]) {
	    flag = true;
	    swap(ca[0], ca[1]);
	}

	assert(ca[0] >= ca[1]);
	
	while (j<k && flip[j].first >= lo) {
	    upd(1,1,k,flip[j].second,flip[j].first);
	    j++;
	}
	
	int p = get(1,1,k,hi);
	// p=0 if every card >= hi

	bool parity = (p==k ? false : qry(1,1,k,p+1,k));
	
	if (flag && p==0) {
	    parity=!parity;
	}
	//cout<<ca[0]<<" "<<ca[1]<<": "<<ca[parity]<<endl;
	
	res += ca[parity];
    }

    cout<<res<<endl;    
    return 0;
}

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