Submission #366325

#	Time	Username	Problem	Language	Result	Execution time	Memory
366325		Rainbowbunny	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	628 ms	21508 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>

int n, k;
int A[200005], B[200005];
int l[200005], r[200005];
int q[200005];

int BIT[600005];
std::vector <int> Q;

void Add(int id, int value)
{
	for(id; id < (int)Q.size(); id += id & -id)
	{
		BIT[id] += value;
	}
}

int Get(int id)
{
	int ans = 0;
	for(id; id > 0; id -= id & -id)
	{
		ans += BIT[id];
	}
	return ans;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> k;
	Q.push_back(0);
	for(int i = 1; i <= n; i++)
	{
		std::cin >> A[i] >> B[i];
		Q.push_back(A[i]);
		Q.push_back(B[i]);
		l[i] = 0;
		r[i] = k;		
	}
	for(int i = 1; i <= k; i++)
	{
		std::cin >> q[i];
		Q.push_back(q[i]);
	}
	std::sort(Q.begin(), Q.end());
	Q.erase(unique(Q.begin(), Q.end()), Q.end());
	for(int i = 1; i <= n; i++)
	{
		A[i] = lower_bound(Q.begin(), Q.end(), A[i]) - Q.begin();
		B[i] = lower_bound(Q.begin(), Q.end(), B[i]) - Q.begin();
	}
	for(int i = 1; i <= k; i++)
	{
		q[i] = lower_bound(Q.begin(), Q.end(), q[i]) - Q.begin();
	}
	for(int turn = 1; turn <= 20; turn++)
	{
		std::vector <std::vector <int> > Query(k + 1, std::vector <int> ());
		for(int i = 1; i <= n; i++)
		{
			int mid = (l[i] + r[i] + 1) >> 1;
			if(l[i] != r[i])
				Query[mid].push_back(i);
		}
		for(int i = 1; i <= Q.size(); i++)
		{
			BIT[i] = 0;
		}
		for(int i = k; i > 0; i--)
		{
			Add(q[i], 1);
			for(auto x : Query[i])
			{
				if(Get(std::min(A[x], B[x]) - 1) != Get(std::max(A[x], B[x]) - 1))
				{
					l[x] = i;
				}
				else
				{
					r[x] = i - 1;
				}
			}
		}
	}
	for(int i = 1; i <= Q.size(); i++)
	{
		BIT[i] = 0;
	}
	long long ans = 0;
	std::vector <std::vector <int> > Query(k + 1, std::vector <int> ());
	for(int i = 1; i <= n; i++)
	{
		Query[l[i]].push_back(i);
	}
	for(int i = k; i >= 0; i--)
	{
		for(auto x : Query[i])
		{
			bool turn = (i == 0) ? 0 : A[x] < B[x];
			int cnt = k - i - Get(std::min(A[x], B[x]) - 1);
			turn ^= (cnt & 1);
			if(turn)
			{
				ans += Q[B[x]];
			}
			else
			{
				ans += Q[A[x]];
			}
		}
		if(i)
		{
			Add(q[i], 1);
		}
	}
	std::cout << ans << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void Add(int, int)':
fortune_telling2.cpp:26:6: warning: statement has no effect [-Wunused-value]
   26 |  for(id; id < (int)Q.size(); id += id & -id)
      |      ^~
fortune_telling2.cpp: In function 'int Get(int)':
fortune_telling2.cpp:35:6: warning: statement has no effect [-Wunused-value]
   35 |  for(id; id > 0; id -= id & -id)
      |      ^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i = 1; i <= Q.size(); i++)
      |                  ~~^~~~~~~~~~~
fortune_telling2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 1; i <= Q.size(); i++)
      |                 ~~^~~~~~~~~~~

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