oj.uz

Submission #234571

# Submission time Handle Problem Language Result Execution time Memory
234571 2020-05-24T16:05:41 Z pedy4000 Tenis (COI19_tenis) C++14
0 / 100
 282 ms 6400 KB 
#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 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 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;
		return ;
	}
	if (r <= s || e <= l)
		return ;
	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

tenis.cpp: In function 'void build(int, int, int)':
tenis.cpp:25: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:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 282 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -