Submission #373223

#	Time	Username	Problem	Language	Result	Execution time	Memory
373223		GioChkhaidze	Tenis (COI19_tenis)	C++14	100 / 100	246 ms	7592 KiB

tenis

#include <bits/stdc++.h>

#define lf (h << 1)
#define rf ((h << 1) | 1)
#define Tree int h, int l, int r
#define Left lf, l, (l + r) >> 1
#define Right rf, ((l + r) >> 1) + 1, r

using namespace std;

const int N = 1e5 + 5;

int n, q, p, x, A, B, tp;
int M[N], a[N][4], v[4 * N], ad[4 * N];

void Shift(Tree) {
	if (!ad[h]) return ;
	v[lf] += ad[h];
	v[rf] += ad[h];
	ad[lf] += ad[h];
	ad[rf] += ad[h];
	ad[h] = 0;
	return ;	
}

void upd(Tree, int L, int R, int dl) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		v[h] += dl;
		ad[h] += dl;
		return ; 
	}
	
	Shift(h, l, r);
	upd(Left, L, R, dl);
	upd(Right, L, R, dl);
	v[h] = min(v[lf], v[rf]);
}

int get(Tree) {
	if (l == r) return r;
	Shift(h, l, r);
	if (!v[lf]) 
		return get(Left);
	return get(Right);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> q;
	for (int j = 0; j < 3; ++j)
		for (int i = 1; i <= n; ++i) {
			cin >> x;
			a[x][j] = i;
			M[x] = max(M[x], i);
		}
	
	for (int i = 1; i <= n; ++i) {
		upd(1, 1, n, i, n, 1);
		upd(1, 1, n, M[i], n, -1);
	}
	
	for (int i = 1; i <= q; ++i) {
		cin >> tp;
		if (tp == 2) {
			cin >> p >> A >> B; --p;
			upd(1, 1, n, M[A], n, 1);
			upd(1, 1, n, M[B], n, 1);

			M[A] = M[B] = 0;
			swap(a[A][p], a[B][p]);
			for (int j = 0; j < 3; ++j) {
				M[A] = max(M[A], a[A][j]);
				M[B] = max(M[B], a[B][j]);
			}

			upd(1, 1, n, M[A], n, -1);
			upd(1, 1, n, M[B], n, -1);
		}
			else
		if (tp == 1) {
			cin >> x;
			if (get(1, 1, n) < M[x]) 
				cout << "NE\n";
					else 
				cout << "DA\n";
		}
	}
}

Compilation message (stderr)

tenis.cpp:48:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main () {
      |       ^

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