Submission #234572

#	Time	Username	Problem	Language	Result	Execution time	Memory
234572		pedy4000	Tenis (COI19_tenis)	C++14	100 / 100	292 ms	7800 KiB

tenis

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
int n, q;
int rann[N][3];
int mn[N << 2];
int lf[N << 2];
int lazy[N << 2];

int getRankMin (int v) {
	return min({rann[v][0], rann[v][1], rann[v][2]});
}

int getRankMax (int v) {
	return max({rann[v][0], rann[v][1], rann[v][2]});
}

void build (int s = 0, int e = n + 1, int id = 1) {
	lf[id] = s;
	if (e - s == 1)
		return ;

	int mid = e + s >> 1;
	build(s, mid, id << 1);
	build(mid, e, id << 1 | 1);
}

void shift (int id) {
	mn[id << 1] += lazy[id];
	lazy[id << 1] += lazy[id];

	mn[id << 1 | 1] += lazy[id];
	lazy[id << 1 | 1] += lazy[id];
	
	lazy[id] = 0;
}

void add (int val, int l, int r, int s = 0, int e = n + 1, int id = 1) {
	if (l <= s && e <= r) {
		mn[id] += val;
		lazy[id] += val;
		return ;
	}
	if (r <= s || e <= l)
		return ;

	if (lazy[id])
		shift(id);

	int mid = e + s >> 1;
	add(val, l, r, s, mid, id << 1);
	add(val, l, r, mid, e, id << 1 | 1);
	mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	lf[id] = lf[id << 1 | 1];
	if (mn[id] == mn[id << 1])
		lf[id] = lf[id << 1];
}

int main() {
	ios::sync_with_stdio(false), cin.tie();
	cin >> n >> q;
	for (int t = 0; t < 3; t++)
		for (int i = 0; i < n; i++) {
			int val;
			cin >> val;
			rann[--val][t] = i;
		}

	build();
	for (int i = 0; i < n; i++)
		if (getRankMin(i) != getRankMax(i))
			add(+1, getRankMin(i), getRankMax(i));
	
	while (q--) {
		int type;
		cin >> type;

		if (type == 1) {
			int x;
			cin >> x;

			if (rann[--x][0] <= lf[1])
				cout << "DA\n";
			else
				cout << "NE\n";
		}
		else {
			int p, a, b;
			cin >> p >> a >> b;
			p--, a--, b--;

			if (getRankMin(a) != getRankMax(a))
				add(-1, getRankMin(a), getRankMax(a));
			if (getRankMin(b) != getRankMax(b))
				add(-1, getRankMin(b), getRankMax(b));
			swap(rann[a][p], rann[b][p]);
			if (getRankMin(a) != getRankMax(a))
				add(+1, getRankMin(a), getRankMax(a));
			if (getRankMin(b) != getRankMax(b))
				add(+1, getRankMin(b), getRankMax(b));
		}
	}
	return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'void build(int, int, int)':
tenis.cpp:26:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
tenis.cpp: In function 'void add(int, int, int, int, int, int)':
tenis.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~

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