oj.uz

Submission #144313

# Submission time Handle Problem Language Result Execution time Memory
144313 2019-08-16T15:38:58 Z emilem Tenis (COI19_tenis) C++14
21 / 100
 75 ms 11060 KB 
#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;
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10928 KB Output is correct
2 Correct 70 ms 10920 KB Output is correct
3 Correct 70 ms 10936 KB Output is correct
4 Correct 68 ms 10928 KB Output is correct
5 Correct 69 ms 11000 KB Output is correct
6 Correct 72 ms 11000 KB Output is correct
7 Correct 73 ms 11000 KB Output is correct
8 Correct 68 ms 11000 KB Output is correct
9 Correct 75 ms 11060 KB Output is correct
10 Correct 70 ms 10940 KB Output is correct
11 Correct 71 ms 10932 KB Output is correct
12 Correct 70 ms 10872 KB Output is correct
13 Correct 71 ms 11000 KB Output is correct
14 Correct 70 ms 10872 KB Output is correct
15 Correct 71 ms 11000 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -