Submission #342242

#	Time	Username	Problem	Language	Result	Execution time	Memory
342242		VodkaInTheJar	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	436 ms	26852 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; 
pair <int, int> a[maxn];
int t[maxn];
void read()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	cin >> a[i].first >> a[i].second;
	
	for (int i = 1; i <= k; i++)
	cin >> t[i];
}

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

void update(int v, int l, int r, int pos, int val)
{
	if (l == r)
	{
		tr[v] = max(tr[v], val);
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	update(v * 2, l, mid, pos, val);
	
	else 
	update(v * 2 + 1, mid + 1, r, pos, val);
	
	merge(v);
}

int get(int v, int l, int r, int ll, int rr)
{
	if (l > rr || r < ll || ll > rr)
	return 0;
	
	if (l >= ll && r <= rr)
	return tr[v];
	
	int mid = (l + r) / 2;
	return max(get(v * 2, l, mid, ll, rr), get(v * 2 + 1, mid + 1, r, ll, rr));
}

int fenw[maxn * 2];
void update_fenw(int pos)
{
	for (; pos <= 2 * n + 1; pos += pos & -pos)
	fenw[pos]++; 
}

int get_pr(int pos)
{
	int ans = 0;
	for (; pos >= 1; pos -= pos & -pos)
	ans += fenw[pos];
	
	return ans;
}

vector <int> v;
vector <int> queries[maxn * 2];
void solve()
{
	for (int i = 1; i <= n; i++)
	{
		v.push_back(a[i].first);
		v.push_back(a[i].second);
	}
	
	sort (v.begin(), v.end());
	
	for (int i = 1; i <= k; i++)
	{
		int pos = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
		if (pos != 2 * n && v[pos] == t[i])
		t[i] = pos + 1;
	
		else 
		t[i] = pos;  
		
	    update(1, 1, 2 * n, t[i], i);
	}
	
	for (int i = 1; i <= n; i++)
	{
		int f = lower_bound(v.begin(), v.end(), a[i].first) - v.begin() + 1, s = lower_bound(v.begin(), v.end(), a[i].second) - v.begin() + 1;
		queries[get(1, 1, 2 * n, min(f, s), max(f, s) - 1)].push_back(i);
	}
	
	long long ans = 0;
	for (int i = k; i >= 0; i--)
	{
		for (auto j: queries[i])
		{
			int curr_pos = lower_bound(v.begin(), v.end(), max(a[j].first, a[j].second)) - v.begin() + 2; 
			int cnt = k - i - get_pr(curr_pos - 1);
			
			if (i == 0)
			ans += (cnt & 1) ? (long long)a[j].second : (long long)a[j].first;
			
			else 
			ans += (cnt & 1) ? (long long)min(a[j].first, a[j].second) : (long long)max(a[j].first, a[j].second);
		}
		
		if (i != 0)
		update_fenw(t[i] + 1);
	}
	
	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: 31 / 31
• Subtask 3: 65 / 65