Submission #957234

#	Time	Username	Problem	Language	Result	Execution time	Memory
957234		lovrot	Tenis (COI19_tenis)	C++17	100 / 100	166 ms	9276 KiB

tenis

#include <algorithm> 
#include <cstdio> 
#include <vector>

using namespace std; 

const int LOG = 17;
const int N = 1 << LOG;
const int OO = 2e9;

int PR[2 * N], M[2 * N], I[2 * N]; 

void propagate(int x) {
	if(x >= N) return;
	M[2 * x] += PR[x];
	M[2 * x + 1] += PR[x];
	PR[2 * x] += PR[x];
	PR[2 * x + 1] += PR[x];
	PR[x] = 0;
}

void update(int l, int r, int val, int x = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l) return;
	if(l <= lo && hi <= r) {
		PR[x] += val;
		M[x] += val;
		return; 
	}
	propagate(x); 
	int mi = (lo + hi) / 2;
	update(l, r, val, 2 * x, lo, mi); 
	update(l, r, val, 2 * x + 1, mi, hi); 
	M[x] = min(M[2 * x], M[2 * x + 1]);
	if(M[x] == M[2 * x]) I[x] = I[2 * x];
	else I[x] = I[2 * x + 1];
}

int n, q, T[3][N];
int P[3][N];

int right(int x) {
	return max({P[0][x], P[1][x], P[2][x]});
}

int main() {
	for(int i = N; i < 2 * N; ++i) I[i] = i - N;

	scanf("%d%d", &n, &q);
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < n; ++j) {
			scanf("%d", &T[i][j]);
			P[i][T[i][j] - 1] = j;
		}
	
	update(n, N, OO);
	for(int i = 0; i < n; ++i) {
		update(i, i + 1, i + 1); 
		update(right(i), N, -1); 
//		printf("%d %d\n", i, right(i));
	}
	
//	printf("%d %d\n", M[1], I[1]);
	for(; q--; ) {
		int t; scanf("%d", &t); 
		
		if(t == 1) {
			int x; scanf("%d", &x); --x;
			printf("%s\n", right(x) <= I[1] ? "DA" : "NE");
		} else {
			int p, a, b; scanf("%d%d%d", &p, &a, &b); --p; --a; --b;
			update(right(a), N, 1); 
			update(right(b), N, 1); 

			swap(P[p][a], P[p][b]);
			swap(T[p][P[p][a]], T[p][P[p][b]]);

			update(right(a), N, -1); 
			update(right(b), N, -1); 
		}
	}
	return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    scanf("%d", &T[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:64:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
tenis.cpp:67:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |    int x; scanf("%d", &x); --x;
      |           ~~~~~^~~~~~~~~~
tenis.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |    int p, a, b; scanf("%d%d%d", &p, &a, &b); --p; --a; --b;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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