Submission #553724

#	Time	Username	Problem	Language	Result	Execution time	Memory
553724		QwertyPi	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	16 ms	1108 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+3;
int A[N], B[N], C[N];
int x1[N], x2[N], pa[N];
map<int, int> M; int m;

struct node{
	node *l, *r;
	int tl, tr, cnt;
	node(int L, int R, int cnt) : l(nullptr), r(nullptr), tl(L), tr(R), cnt(cnt){};
	~node(){};
};

void build(node*& t, int l, int r){
	t = new node(l, r, 0);
	if(l == r) return;
	int mid = (l + r) / 2;
	build(t->l, l, mid); 
	build(t->r, mid + 1, r);
}

node* upd(node* t, int tl, int tr, int q, int delta){
	if(tl == tr){
		node* ret = new node(tl, tr, (t ? 0 : t->cnt) + delta);
		return ret;
	}
	int tm = (tl + tr) / 2;
	node* ret = new node(tl, tr, t->cnt);
	ret->l = t->l, ret->r = t->r;
	if(q <= tm){
		ret->l = upd(t->l, tl, tm, q, delta);
	}else{
		ret->r = upd(t->r, tm + 1, tr, q, delta);
	}
	ret->cnt = (ret->l ? ret->l->cnt : 0) + (ret->r ? ret->r->cnt : 0);
	cout << ret->tl << ' ' << ret->tr << ' ' << ret->cnt << endl;
	return ret;
}

int qry(node* t, int r){
	if(t->tl == t->tr) return t->cnt;
	if(r <= t->l->tr) return qry(t->l, r);
	else return t->l->cnt + qry(t->r, r);
}

int qry(node* t, int l, int r){
	return qry(t, r) - qry(t, l - 1);
}

node* T[N];

int32_t main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> A[i] >> B[i];
		x1[i] = min(A[i], B[i]);
		x2[i] = max(A[i], B[i]);
		pa[i] = x1[i] != A[i];
	}
	for(int i = 1; i <= k; i++){
		cin >> C[i];
	}
	{
		vector<int> v; for(int i = 1; i <= k; i++) v.push_back(C[i]);
		sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin());
		int idx = 0; for(auto i : v) M[i] = ++idx; M[1 << 30] = ++idx; m = idx;
		for(int i = 1; i <= k; i++) C[i] = M[C[i]];
	}
	
	build(T[0], 0, m);
	for(int i = 1; i <= k; i++){
		T[i] = upd(T[i - 1], 0, m, C[i], 1);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++){
		int y1 = M.lower_bound(x1[i])->second;
		int y2 = M.lower_bound(x2[i])->second;
		int l = 0, r = k, tot = qry(T[k], y1, y2 - 1);
		while(l != r){
			int mid = (l + r) / 2;
			if(qry(T[mid], y1, y2 - 1) == tot){
				r = mid;
			}else{
				l = mid + 1;
			}
		}
		if(l != 0) pa[i] = true;
		int cnt = qry(T[k], y2, m) - qry(T[l], y2, m);
		pa[i] ^= cnt % 2;
		ans += pa[i] ? x2[i] : x1[i];
	}
	cout << ans << endl;
}

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