제출 #144313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144313		emilem	Tenis (COI19_tenis)	C++14	21 / 100	75 ms	11060 KiB

tenis

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

vector<int> ranking[4], 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 (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] = max(tree[v * 2], tree[v * 2 + 1]);
	tree[v].first += lazy[v];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, q;
	cin >> n >> q;
	ranking[1] = ranking[2] = ranking[3] = vector<int>(n + 1);
	rankAt[1] = rankAt[2] = rankAt[3] = vector<int>(n + 1);
	for (int p = 1; p <= 3; ++p)
		for (int i = 1; i <= n; ++i)
		{
			cin >> ranking[p][i];
			rankAt[p][ranking[p][i]] = i;
		}
	vector<int> worst(n + 1, 0);
	for (int p = 1; p <= 3; ++p)
		for (int i = 1; i <= n; ++i)
			worst[ranking[p][i]] = max(worst[ranking[p][i]], i);
	vector<int> f(n + 1);
	for (int i = 1; i <= n; ++i)
		++f[worst[i]];
	for (int i = 2; i <= n; ++i)
		f[i] += f[i - 1];
	/*
	for (int i = 1; i <= n; ++i)
		cout << worst[i] << ' ';
	cout << endl;
	for (int i = 1; i <= n; ++i)
		cout << f[i] << ' ';
	cout << endl;
	*/
	tree.resize(n * 4);
	lazy.resize(n * 4);
	int winnerBound = 0;
	for (int i = 1; i <= n; ++i)
		f[i] = i - f[i];
	Build(1, 1, n, f);
	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(ranking[p][rankAt[p][a]], ranking[p][rankAt[p][b]]);
			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;
}

컴파일 시 표준 에러 (stderr) 메시지

tenis.cpp: In function 'int main()':
tenis.cpp:76:6: warning: unused variable 'winnerBound' [-Wunused-variable]
  int winnerBound = 0;
      ^~~~~~~~~~~

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