Submission #366320

#	Time	Username	Problem	Language	Result	Execution time	Memory
366320		Rainbowbunny	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	3070 ms	26272 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[200005];

void Add(int id, int value)
{
	for(id; id <= k; 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;
	for(int i = 1; i <= n; i++)
	{
		std::cin >> A[i] >> B[i];
		l[i] = 0;
		r[i] = k;		
	}
	for(int i = 1; i <= k; i++)
	{
		std::cin >> q[i];
	}
	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);
		}
		std::set <int> S;
		for(int i = k; i > 0; i--)
		{
			S.insert(q[i]);
			for(auto x : Query[i])
			{
				auto value = S.lower_bound(std::min(A[x], B[x]));
				if(value != S.end() and *value < std::max(A[x], B[x]))
				{
					l[x] = i;
				}
				else
				{
					r[x] = i - 1;
				}
			}
		}
	}
	long long ans = 0;
	std::vector <std::vector <int> > Query(k + 1, std::vector <int> ());
	std::vector <int> Q;
	for(int i = 1; i <= k; i++)
	{
		Q.push_back(q[i]);
	}
	Q.push_back(0);
	std::sort(Q.begin(), Q.end());
	Q.erase(unique(Q.begin(), Q.end()), Q.end());
	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(lower_bound(Q.begin(), Q.end(), std::max(A[x], B[x])) - Q.begin() - 1);
			turn ^= (cnt & 1);
			if(turn)
			{
				ans += B[x];
			}
			else
			{
				ans += A[x];
			}
		}
		if(i)
		{
			Add(lower_bound(Q.begin(), Q.end(), q[i]) - Q.begin(), 1);
		}
	}
	std::cout << ans << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void Add(int, int)':
fortune_telling2.cpp:25:6: warning: statement has no effect [-Wunused-value]
   25 |  for(id; id <= k; id += id & -id)
      |      ^~
fortune_telling2.cpp: In function 'int Get(int)':
fortune_telling2.cpp:34:6: warning: statement has no effect [-Wunused-value]
   34 |  for(id; id > 0; id -= id & -id)
      |      ^~

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