fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3. using namespace std;
  4.  
  5. using ll = long long;
  6.  
  7. template <typename K, typename V, typename Comp = std::less<K>>
  8. using order_statistic_map = __gnu_pbds::tree<
  9. 	K, V, Comp,
  10. 	__gnu_pbds::rb_tree_tag,
  11. 	__gnu_pbds::tree_order_statistics_node_update
  12. >;
  13.  
  14. template <typename K, typename Comp = std::less<K>>
  15. using order_statistic_set = order_statistic_map<K, __gnu_pbds::null_type, Comp>;
  16.  
  17. const int MAXN = 2.1e5;
  18. const int MAXQ = 2.1e5;
  19. int n, q;
  20. int ca[MAXN];
  21. int cb[MAXN];
  22. int qt[MAXQ];
  23.  
  24. const int S = 1 << 19;
  25. int seg[2 * S];
  26.  
  27. void update(int i, int v) {
  28. 	if (seg[S+i] >= v) return;
  29. 	seg[S+i] = v;
  30. 	for (int a = (S+i)/2; a; a /= 2) {
  31. 		seg[a] = max(seg[2*a], seg[2*a+1]);
  32. 	}
  33. }
  34.  
  35. int query(int l) {
  36. 	int res = -1;
  37. 	for (int a = S+l, b = S+S; a < b; a /= 2, b /= 2) {
  38. 		if (a & 1) {
  39. 			res = max(res, seg[a++]);
  40. 		}
  41. 		if (b & 1) {
  42. 			res = max(res, seg[--b]);
  43. 		}
  44. 	}
  45. 	return res;
  46. }
  47.  
  48. int main() {
  49. 	ios::sync_with_stdio(0), cin.tie(0);
  50.  
  51. 	cin >> n >> q;
  52. 	vector<int> vals;
  53. 	for (int i = 0; i < n; i++) {
  54. 		cin >> ca[i] >> cb[i];
  55. 		vals.push_back(min(ca[i], cb[i]));
  56. 	}
  57. 	for (int i = 0; i < q; i++) {
  58. 		cin >> qt[i];
  59. 		vals.push_back(qt[i]);
  60. 	}
  61.  
  62. 	sort(vals.begin(), vals.end());
  63. 	vals.erase(unique(vals.begin(), vals.end()), vals.end());
  64. 	auto lookup = [&](int v) {
  65. 		auto it = lower_bound(vals.begin(), vals.end(), v);
  66. 		assert(it != vals.end() && *it == v);
  67. 		return int(it - vals.begin());
  68. 	};
  69.  
  70. 	vector<int> cards(n);
  71. 	iota(cards.begin(), cards.end(), 0);
  72. 	sort(cards.begin(), cards.end(), [&](int i, int j) {
  73. 		return max(ca[i], cb[i]) < max(ca[j], cb[j]);
  74. 	});
  75. 	vector<int> operations(q);
  76. 	iota(operations.begin(), operations.end(), 0);
  77. 	sort(operations.begin(), operations.end(), [&](int i, int j) {
  78. 		return qt[i] < qt[j];
  79. 	});
  80.  
  81. 	order_statistic_set<pair<int, int>> os;
  82. 	for (int i = 0; i < q; i++) {
  83. 		os.insert({i, qt[i]});
  84. 	}
  85. 	auto operations_it = operations.begin();
  86. 	ll ans = 0;
  87. 	for (int a = 1; a < S*2; a++) {
  88. 		seg[a] = -1;
  89. 	}
  90. 	for (auto card : cards) {
  91. 		int lo = min(ca[card], cb[card]);
  92. 		int hi = max(ca[card], cb[card]);
  93. 		while (operations_it != operations.end() && qt[*operations_it] < hi) {
  94. 			os.erase({*operations_it, qt[*operations_it]});
  95. 			update(lookup(qt[*operations_it]), *operations_it);
  96. 			operations_it++;
  97. 		}
  98.  
  99. 		int last_time = query(lookup(lo));
  100. 		int parity = (os.size() - os.order_of_key({last_time, -1})) % 2;
  101. 		if (last_time == -1) {
  102. 			ans += parity ? cb[card] : ca[card];
  103. 		} else {
  104. 			ans += parity ? lo : hi;
  105. 		}
  106. 	}
  107. 	cout << ans << '\n';
  108.  
  109. 	return 0;
  110. }
  111.  
  112. // Let's assume that a_i < b_i
  113. // t_j < a_i: nothing happens
  114. // a_i <= t_j < b_i: becomes b_i
  115. // b_i <= t_j: flips
  116. // For each card, let's fix the last operation of the second type, then the result only depends on the parity of (# of flips) after that operation
  117.  
Success #stdin #stdout 0s 7724KB
comments (?)
stdin
copy 
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
stdout
copy 
18
https://ideone.com/6GdMtz
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!