Submission #917034

#	Time	Username	Problem	Language	Result	Execution time	Memory
917034		NK_	Tenis (COI19_tenis)	C++17	100 / 100	245 ms	9168 KiB

tenis

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
using vi = V<int>;

struct Seg {
	const int ID = 0; int comb(int a, int b) { return min(a, b); }
	vi seg, lazy; int N; void init(int n) {
		for(N = 1; N < n;) N *= 2;
		seg.assign(2 * N, ID); lazy.assign(2 * N, ID);
	}

	void push(int x, int L, int R) {
		seg[x] += lazy[x];
		if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
		lazy[x] = 0;
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void upd(int l, int v, int x, int L, int R) { // the suffix starting at l
		push(x, L, R); if (R < l) return;
		// cout << L << " <-> " << R << endl;
		if (l <= L) { lazy[x] += v; push(x, L, R); return; }
		int M = (L + R) / 2; upd(l, v, 2 * x, L, M); upd(l, v, 2 * x + 1, M + 1, R);
		pull(x);
	}

	void full(int x, int L, int R) {
		push(x, L, R);
		if (L == R) return;
		int M = (L + R) / 2; full(2 * x, L, M); full(2 * x + 1, M + 1, R);
		pull(x);
	}


	int find(int x, int L, int R) { // find first zero
		push(x, L, R); if (seg[x] > 0) return -1;
		if (L == R) return L;
		int M = (L + R) / 2;
		int res = find(2 * x, L, M);
		if (res == -1) return find(2 * x + 1, M + 1, R);
		return res;
	}

	void upd(int l, int v) { upd(l, v, 1, 0, N - 1); }
	int find() { return find(1, 0, N - 1); }
	void full() { full(1, 0, N - 1); }
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;

	V<vi> A(3, vi(N));
	for(int t = 0; t < 3; t++) for(int i = 0; i < N; i++) { int x; cin >> x; --x; A[t][x] = i; }

	Seg st; st.init(2 * (N + 1));

	// cout << 1 << endl;

	auto upd = [&](int i, int d = +1) {
		// cout << i << endl;
		int l = min({A[0][i], A[1][i], A[2][i]}), r = max({A[0][i], A[1][i], A[2][i]});
		// cout << l << " " << r + 1 << endl;
		st.upd(2 * l, +1 * d); st.upd(2 * r + 1, -1 * d); 
	};

	for(int i = 0; i < N; i++) upd(i);

	// cout << 1 << endl;

	// st.full();
	// for(int i = 0; i <= 2 * N; i++) cout << i << " => " << st.seg[i + st.N] << endl;
	// cout << endl;
	
	for(int q = 0; q < Q; q++) {

		// st.full();
		// for(int i = 0; i <= 2 * N; i++) cout << i << " => " << st.seg[i + st.N] << endl;
		// cout << endl;

		int t; cin >> t;
		if (t == 1) {
			int x; cin >> x; --x;
			int fir = st.find() / 2; 
			// cout << "FIR: " << fir << endl;
			cout << (A[0][x] <= fir ? "DA" : "NE") << nl;
		} else {
			int c, x, y; cin >> c >> x >> y; --c, --x, --y;
			
			upd(x, -1); upd(y, -1);
			swap(A[c][x], A[c][y]);
			upd(x); upd(y);
		}
	}

	exit(0-0);
}

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