Submission #52224

#	Time	Username	Problem	Language	Result	Execution time	Memory
52224		kriii	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	678 ms	39704 KiB

fortune_telling2

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int Z = 1 << 18;
vector<int> G[Z * 2];
int N, K, A[200200], B[200200], T[200200];

int cnt(int x, int l, int r)
{
	auto &v = G[x];
	return upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
}

int cnt(int x, int y, int l, int r)
{
	int res = 0;
	x += Z; y += Z;
	while (x < y) {
		if (x & 1) res += cnt(x++, l, r);
		if (~y & 1) res += cnt(y--, l, r);
		x /= 2; y /= 2;
	} if (x == y) res += cnt(x, l, r);
	return res;
}

int get(int l, int r)
{
	int x = 1;
	while (x < Z) {
		x *= 2; x++;
		if (cnt(x, l, r) == 0) x--;
	}
	return x - Z;
}

int main()
{
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) scanf("%d %d", &A[i], &B[i]);
	for (int j = 0; j < K; j++) {
		scanf("%d", &T[j]);
		G[j + Z].push_back(T[j]);
	}

	for (int i = Z - 1; i >= 1; i--) {
		vector<int> &a = G[i * 2];
		vector<int> &b = G[i * 2 + 1];
		vector<int> &c = G[i]; c.reserve(a.size() + b.size());
		int p = 0, q = 0;
		while (p < a.size() && q < b.size()) {
			if (a[p] < b[q]) c.push_back(a[p++]);
			else c.push_back(b[q++]);
		}
		while (p < a.size()) c.push_back(a[p++]);
		while (q < b.size()) c.push_back(b[q++]);
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		int p = 0;
		if (min(A[i], B[i]) != max(A[i], B[i])) {
			p = get(min(A[i], B[i]), max(A[i], B[i]) - 1);
		}
		int q = cnt(p, K-1, max(A[i], B[i]), 0x7fffffff);
		if (p && A[i] < B[i]) swap(A[i], B[i]);
		if (q & 1) swap(A[i], B[i]);
		ans += A[i];
	}
	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:52:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < a.size() && q < b.size()) {
          ~~^~~~~~~~~~
fortune_telling2.cpp:52:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < a.size() && q < b.size()) {
                          ~~^~~~~~~~~~
fortune_telling2.cpp:56:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < a.size()) c.push_back(a[p++]);
          ~~^~~~~~~~~~
fortune_telling2.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (q < b.size()) c.push_back(b[q++]);
          ~~^~~~~~~~~~
fortune_telling2.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:41:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%d %d", &A[i], &B[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T[j]);
   ~~~~~^~~~~~~~~~~~~

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