Submission #144383

#	Time	Username	Problem	Language	Result	Execution time	Memory
144383		emilem	Tenis (COI19_tenis)	C++14	100 / 100	218 ms	7416 KiB

tenis

#include <iostream>
#include <vector>
using namespace std;

vector<int> rankAt[4];
vector< pair<int, int> > tree;
vector<int> lazy;

void Build(int v, int vl, int vr, const vector<int>& a)
{
	if (vl == vr)
	{
		tree[v] = make_pair(a[vr], vr);
		return;
	}
	int vm = vl + (vr - vl) / 2;
	Build(v * 2, vl, vm, a);
	Build(v * 2 + 1, vm + 1, vr, a);
	tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}
void Update(int v, int vl, int vr, int l, int r, int val)
{
	/*
	if (l == 2 && r == 4)
		cerr << "";
	*/
	if (vl == l && vr == r)
	{
		tree[v].first += val;
		lazy[v] += val;
		return;
	}
	int vm = vl + (vr - vl) / 2;
	if (r <= vm)
		Update(v * 2, vl, vm, l, r, val);
	else if (l > vm)
		Update(v * 2 + 1, vm + 1, vr, l, r, val);
	else
	{
		Update(v * 2, vl, vm, l, vm, val);
		Update(v * 2 + 1, vm + 1, vr, vm + 1, r, val);
	}
	tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
	tree[v].first += lazy[v];
}
int Query(int v, int vl, int vr, int l, int r)
{
	if (vl == l && vr == r)
		return tree[v].first;
	int vm = vl + (vr - vl) / 2;
	if (r <= vm)
		return Query(v * 2, vl, vm, l, r) + lazy[v];
	else if (l > vm)
		return Query(v * 2 + 1, vm + 1, vr, l, r) + lazy[v];
	else
		return max(Query(v * 2, vl, vm, l, vm), Query(v * 2 + 1, vm + 1, vr, vm + 1, r)) + lazy[v];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, q;
	cin >> n >> q;
	rankAt[1] = rankAt[2] = rankAt[3] = vector<int>(n + 1);
	vector<int> worst(n + 1, 0);
	for (int p = 1; p <= 3; ++p)
		for (int i = 1; i <= n; ++i)
		{
			int ranking;
			cin >> ranking;
			rankAt[p][ranking] = i;
			worst[ranking] = max(worst[ranking], i);
		}
	tree.resize(n * 4);
	lazy.resize(n * 4);
	vector<int> f(n + 1);
	for (int i = 1; i <= n; ++i)
		f[i] += i;
	Build(1, 1, n, f);
	for (int i = 1; i <= n; ++i)
	{
		Update(1, 1, n, worst[i], n, -1);
		/*
		for (int ii = 1; ii <= n; ++ii)
			cout << Query(1, 1, n, ii, ii) << ' ';
		cout << ": " << tree[1].first;
		cout << endl;
		*/
	}
	/*
	cout << endl;
	*/
	while (q--)
	{
		int type;
		cin >> type;
		if (type == 1)
		{
			int man;
			cin >> man;
			cout << (worst[man] <= tree[1].second ? "DA\n" : "NE\n");
		}
		else
		{
			int p, a, b;
			cin >> p >> a >> b;
			Update(1, 1, n, worst[a], n, 1);
			Update(1, 1, n, worst[b], n, 1);
			swap(rankAt[p][a], rankAt[p][b]);
			worst[a] = max(max(rankAt[1][a], rankAt[2][a]), rankAt[3][a]);
			worst[b] = max(max(rankAt[1][b], rankAt[2][b]), rankAt[3][b]);
			Update(1, 1, n, worst[a], n, -1);
			Update(1, 1, n, worst[b], n, -1);
		}
	}

	char I;
	cin >> I;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49