Submission #845997

#	Time	Username	Problem	Language	Result	Execution time	Memory
845997		haninak697	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	574 ms	229312 KiB

fortune_telling2

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

using ll = long long;

#define left defined_left
#define right defined_right

const int N = 2e5 + 5, Q = N;

int n, q, a[N], b[N], t[Q], sp[__lg(N) + 5][N * 4], m;
vector<int> arr = {0};

int get(int x) {
	return lower_bound(arr.begin(), arr.end(), x) - arr.begin();
}

int get_max(int l, int r) {
	int k = __lg(r - l + 1);
	return max(sp[k][l], sp[k][r - (1 << k) + 1]);
}

struct Node {
	int sum;
	Node *left, *right;
	
	Node(int sum = 0, Node *left = nullptr, Node *right = nullptr): 
		sum(sum), left(left), right(right) {}
	
	Node *go_left() {
		if (left == nullptr)
			left = new Node();
		return left;
	}
	
	Node *go_right() {
		if (right == nullptr)
			right = new Node();
		return right;
	}
};

Node *v[N];

Node* update(int x, Node *cur, int l, int r) {
	if (l == r) return new Node(cur->sum + 1);
	int mid = (l + r) / 2;
	Node *res = new Node();
	if (x <= mid) {
		res->left = update(x, cur->go_left(), l, mid);
		res->right = cur->go_right();
	} else {
		res->left = cur->go_left();
		res->right = update(x, cur->go_right(), mid + 1, r);
	}
	res->sum = res->go_left()->sum + res->go_right()->sum;
	return res;
}

int get_sum(int x, int y, Node *cur, int l, int r) {
	if (l > y || r < x) return 0;
	if (x <= l && r <= y) return cur->sum;
	int mid = (l + r) / 2;
	return get_sum(x, y, cur->go_left(), l, mid) + get_sum(x, y, cur->go_right(), mid + 1, r);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  if (fopen("SwapCard.inp", "r"))
  	freopen("SwapCard.inp", "r", stdin),
  	freopen("SwapCard.out", "w", stdout);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
  	cin >> a[i] >> b[i];
  	arr.emplace_back(a[i]);
  	arr.emplace_back(b[i]);
  }
  for (int i = 1; i <= q; i++) {
  	cin >> t[i];
  	arr.emplace_back(t[i]);
  }
  sort(arr.begin(), arr.end());
  arr.resize(unique(arr.begin(), arr.end()) - arr.begin());
  m = arr.size() - 1;
  for (int i = 1; i <= n; i++)
  	a[i] = get(a[i]), b[i] = get(b[i]);
  for (int i = 1; i <= q; i++) {
  	t[i] = get(t[i]);
  	sp[0][t[i]] = i;
  }
  // cerr << arr[2] << '\n';
  // cerr << sp[0][2] << '\n';
  v[q + 1] = new Node();
  for (int i = q; i > 0; i--) 
  	v[i] = update(t[i], v[i + 1], 1, m);
  for (int k = 1; (1 << k) <= m; k++)
  	for (int i = 1; i + (1 << k) - 1 <= m; i++)
  		sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
  	if (a[i] == b[i]) {
  		ans += arr[a[i]];
  		continue;
  	}
  	bool dummy = false;
  	if (a[i] < b[i]) {
  		dummy = true;
  		swap(a[i], b[i]);
  	}
  	int pos = get_max(b[i], a[i] - 1);
  	// cerr << arr[b[i]] << ' ' << arr[a[i] - 1] << '\n';
  	// cerr << "pos = " << pos << '\n';
  	bool greater_ = 1 ^ (get_sum(a[i], m, v[pos + 1], 1, m) & 1);
  	if (pos == 0) greater_ ^= dummy;
  	int cur;
  	if (greater_) cur = arr[a[i]];
  	else cur = arr[b[i]];
  	ans += cur;
  }
  cout << ans;
  return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:70:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |    freopen("SwapCard.inp", "r", stdin),
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |    freopen("SwapCard.out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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