oj.uz

Submission #236319

# Submission time Handle Problem Language Result Execution time Memory
236319 2020-06-01T10:27:57 Z ArshiaDadras Tenis (COI19_tenis) C++17
18 / 100
 500 ms 6776 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, q, a[N][3], pos[N][3];
struct Segment {
	int seg[N << 1];

	void build(int id1, int id2, int id = 1, int st = 0, int en = n) {
		if (en - st == 1) {
			seg[id] = pos[a[st][id1]][id2];
			return;
		}
		int mid = (st + en) / 2;
		build(id1, id2, id << 1, st, mid);
		build(id1, id2, id << 1 | 1, mid, en);
		seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	}
	void change(int p, int x, int id = 1, int st = 0, int en = n) {
		if (en - st == 1) {
			seg[id] = x;
			return;
		}
		int mid = (st + en) / 2;
		if (p < mid)
			change(p, x, id << 1, st, mid);
		else
			change(p, x, id << 1 | 1, mid, en);
		seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	}
	int get(int l, int r = n, int id = 1, int st = 0, int en = n) {
		if (r <= st || en <= l)
			return n;
		if (l <= st && en <= r)
			return seg[id];
		int mid = (st + en) / 2;
		return min(get(l, r, id << 1, st, mid), get(l, r, id << 1 | 1, mid, en));
	}
} seg[3];

void read_input() {
	cin >> n >> q;
	for (int t = 0; t < 3; t++)
		for (int i = 0; i < n; i++) {
			int p;
			cin >> p;
			a[i][t] = --p;
			pos[p][t] = i;
		}
}

void solve() {
	seg[0].build(0, 1);
	seg[1].build(1, 2);
	seg[2].build(2, 0);
}

void write_output() {
	while (q--) {
		int t;
		cin >> t;
		if (t & 1) {
			int p;
			cin >> p;
			p = pos[p - 1][0];
			while (true) {
				int prv = p;
				p = seg[0].get(p);
				p = seg[1].get(p);
				p = seg[2].get(p);
				if (p == prv)
					break;
			}
			cout << (p? "NE\n": "DA\n");
		}
		else {
			int p, a, b;
			cin >> p >> a >> b;
			int prv = (p + 1) % 3, nxt = p-- % 3;
			swap(pos[--a][p], pos[--b][p]);
			seg[p].change(pos[a][p], pos[a][nxt]);
			seg[p].change(pos[b][p], pos[b][nxt]);
			seg[prv].change(pos[a][prv], pos[a][p]);
			seg[prv].change(pos[b][prv], pos[b][p]);
		}
	}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Incorrect 40 ms 6776 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 5092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Incorrect 40 ms 6776 KB Output isn't correct
14 Halted 0 ms 0 KB -