Submission #335916

#	Time	Username	Problem	Language	Result	Execution time	Memory
335916		VodkaInTheJar	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3093 ms	1772 KiB

fortune_telling2

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 2e5 + 3;

int n, k;
int a[maxn], b[maxn];
int t[maxn];
void read()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	cin >> a[i] >> b[i];
	
	for (int i = 1; i <= k; i++)
	cin >> t[i];
}

int tr[maxn * 4];

void merge(int v)
{
	tr[v] = max(tr[v * 2], tr[v * 2 + 1]);
}

void build(int v, int l, int r)
{
	if (l == r)
	{
		tr[v] = t[l];
		return;
	}
	
	int mid = (l + r) / 2;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	
	merge(v); 
}

int first, second;
void f(int v, int l, int r)
{
 	if (tr[v] < first)
	return;
	
	if (l == r)
	{
		swap(first, second);
		return;
	}
	
	int mid = (l + r) / 2; 
	f(v * 2, l, mid);
	f(v * 2 + 1, mid + 1, r);
}

void solve()
{
	build(1, 1, k);
	
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		first = a[i], second = b[i];
		f(1, 1, k);
		
		ans += first;
	}
	
	cout << ans << endl; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	read();
	solve();
}

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