제출 #553747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553747		QwertyPi	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	1643 ms	261712 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

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

// persistent segment tree
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 ? t->cnt : 0) + 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);
	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];

// MT merge sort tree

namespace MTree{
	vector<int> t[N * 4];
	vector<int> a, b;
	void build(int v, int l, int r){
		if(l == r){
			t[v].push_back(C[l + 1]);
			return;
		}
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m + 1, r);
		merge(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v * 2 + 2].begin(), t[v * 2 + 2].end(), back_inserter(t[v]));
	}
	int last(int v, int l, int r, int vl, int vr){
		if(l == r) return l;
		if(lower_bound(t[v * 2 + 2].begin(), t[v * 2 + 2].end(), vl) != upper_bound(t[v * 2 + 2].begin(), t[v * 2 + 2].end(), vr)){
			return last(v * 2 + 2, (l + r) / 2 + 1, r, vl, vr);
		}else{
			return last(v * 2 + 1, l, (l + r) / 2, vl, vr);
		}
	}
};

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]];
	}
	
	MTree::build(0, 0, k - 1);
	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 = MTree::last(0, 0, k - 1, y1, y2 - 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: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65