Submission #656691

#	Time	Username	Problem	Language	Result	Execution time	Memory
656691		TranGiaHuy1508	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	6 ms	4436 KiB

fortune_telling2

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

struct MaxImplicitSegtree{
	int lb, rb;
	MaxImplicitSegtree *leftnode, *rightnode;
	int mx;

	MaxImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), mx(-1) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new MaxImplicitSegtree(lb, mid);
		rightnode = new MaxImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return mx;
		if (lb > r || rb < l) return -1;

		extend();
		return max(leftnode->get(l, r), rightnode->get(l, r));
	}

	void update(int x, int val){
		if (lb == x && rb == x) mx = val;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, val);
			else rightnode->update(x, val);

			mx = max(leftnode->mx, rightnode->mx);
		}
	}
};

struct SumImplicitSegtree{
	int lb, rb;
	SumImplicitSegtree *leftnode, *rightnode;
	int sum;

	SumImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), sum(0) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new SumImplicitSegtree(lb, mid);
		rightnode = new SumImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return sum;
		if (lb > r || rb < l) return 0;

		extend();
		return leftnode->get(l, r) + rightnode->get(l, r);
	}

	void update(int x, int delta){
		if (lb == x && rb == x) sum += delta;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, delta);
			else rightnode->update(x, delta);

			sum = leftnode->sum + rightnode->sum;
		}
	}
};

const int inf = 1e9 + 1;
int n, q;
vector<pair<int, int>> cards;
vector<int> MN, MX, qs, lst, inv;

void main_program(){
	cin >> n >> q;
	qs.resize(q);
	cards.resize(n);
	MN.resize(n);
	MX.resize(n);
	lst.assign(n, -1);
	inv.assign(n, 0);

	for (int i = 0; i < n; i++){
		int A, B; cin >> A >> B;
		cards[i] = {A, B};
		MN[i] = min(A, B); MX[i] = max(A, B);
	}

	MaxImplicitSegtree ist(1, inf);
	SumImplicitSegtree sst(1, inf);

	for (int i = 0; i < q; i++){
		cin >> qs[i];
		ist.update(qs[i], i);
	}

	for (int i = 0; i < n; i++){
		if (MX[i] > MN[i]) lst[i] = ist.get(MN[i], MX[i] - 1);
	}

	// for (int i = 0; i < n; i++) cout << lst[i] << " ";
	// cout << "\n";

	vector<vector<int>> radix(q + 1);
	for (int i = 0; i < n; i++)	radix[lst[i] + 1].push_back(i);

	for (int i = q-1; i >= 0; i--){
		sst.update(qs[i], 1);
		for (auto j: radix[i]){
			inv[j] = sst.get(MX[i], inf);
		}
	}

	// for (int i = 0; i < n; i++) cout << inv[i] << " ";
	// cout << "\n";

	long long res = 0;
	for (int i = 0; i < n; i++){
		int crr;
		if (lst[i] >= 0) crr = MX[i];
		else crr = cards[i].first;

		if (inv[i] & 1) crr = cards[i].first + cards[i].second - crr;

		// cout << crr << "\n";
		res += crr;
	}

	cout << res << "\n";
}

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