Submission #236319

#	Time	Username	Problem	Language	Result	Execution time	Memory
236319		ArshiaDadras	Tenis (COI19_tenis)	C++17	18 / 100	1094 ms	6776 KiB

tenis

/* 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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49