oj.uz

Submission #845997

# Submission time Handle Problem Language Result Execution time Memory
845997 2023-09-07T03:14:23 Z haninak697 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 574 ms 229312 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 4 ms 27740 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27736 KB Output is correct
6 Correct 4 ms 27484 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27480 KB Output is correct
9 Correct 4 ms 27480 KB Output is correct
10 Correct 4 ms 25432 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27480 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 4 ms 27740 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27736 KB Output is correct
6 Correct 4 ms 27484 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27480 KB Output is correct
9 Correct 4 ms 27480 KB Output is correct
10 Correct 4 ms 25432 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27480 KB Output is correct
14 Correct 24 ms 42064 KB Output is correct
15 Correct 43 ms 53716 KB Output is correct
16 Correct 62 ms 67924 KB Output is correct
17 Correct 84 ms 77352 KB Output is correct
18 Correct 85 ms 77268 KB Output is correct
19 Correct 84 ms 77364 KB Output is correct
20 Correct 86 ms 77316 KB Output is correct
21 Correct 79 ms 76748 KB Output is correct
22 Correct 66 ms 70376 KB Output is correct
23 Correct 62 ms 64976 KB Output is correct
24 Correct 60 ms 63696 KB Output is correct
25 Correct 68 ms 73520 KB Output is correct
26 Correct 67 ms 70372 KB Output is correct
27 Correct 75 ms 70860 KB Output is correct
28 Correct 71 ms 70864 KB Output is correct
29 Correct 92 ms 74448 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 4 ms 27740 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27736 KB Output is correct
6 Correct 4 ms 27484 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27480 KB Output is correct
9 Correct 4 ms 27480 KB Output is correct
10 Correct 4 ms 25432 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27480 KB Output is correct
14 Correct 24 ms 42064 KB Output is correct
15 Correct 43 ms 53716 KB Output is correct
16 Correct 62 ms 67924 KB Output is correct
17 Correct 84 ms 77352 KB Output is correct
18 Correct 85 ms 77268 KB Output is correct
19 Correct 84 ms 77364 KB Output is correct
20 Correct 86 ms 77316 KB Output is correct
21 Correct 79 ms 76748 KB Output is correct
22 Correct 66 ms 70376 KB Output is correct
23 Correct 62 ms 64976 KB Output is correct
24 Correct 60 ms 63696 KB Output is correct
25 Correct 68 ms 73520 KB Output is correct
26 Correct 67 ms 70372 KB Output is correct
27 Correct 75 ms 70860 KB Output is correct
28 Correct 71 ms 70864 KB Output is correct
29 Correct 92 ms 74448 KB Output is correct
30 Correct 274 ms 186340 KB Output is correct
31 Correct 332 ms 200136 KB Output is correct
32 Correct 414 ms 211060 KB Output is correct
33 Correct 559 ms 228104 KB Output is correct
34 Correct 253 ms 184264 KB Output is correct
35 Correct 555 ms 227260 KB Output is correct
36 Correct 556 ms 227492 KB Output is correct
37 Correct 563 ms 228476 KB Output is correct
38 Correct 544 ms 228344 KB Output is correct
39 Correct 574 ms 227516 KB Output is correct
40 Correct 508 ms 223232 KB Output is correct
41 Correct 556 ms 227408 KB Output is correct
42 Correct 573 ms 229312 KB Output is correct
43 Correct 378 ms 220272 KB Output is correct
44 Correct 375 ms 219348 KB Output is correct
45 Correct 385 ms 220448 KB Output is correct
46 Correct 376 ms 201704 KB Output is correct
47 Correct 356 ms 187684 KB Output is correct
48 Correct 460 ms 214876 KB Output is correct
49 Correct 436 ms 214460 KB Output is correct