Submission #117937

#	Time	Username	Problem	Language	Result	Execution time	Memory
117937		imyujin	Tenis (COI19_tenis)	C++14	18 / 100	1067 ms	5940 KiB

tenis

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 100005

int N, Q;
int r[3][MAXN];
int idx[3][MAXN];
bool chk[MAXN];
int seg[3 * MAXN], lazy[3 * MAXN];

int minidx(int x) {
	return idx[0][x] < idx[1][x] ? (idx[0][x] < idx[2][x] ? idx[0][x] : idx[2][x]) : (idx[1][x] < idx[2][x] ? idx[1][x] : idx[2][x]);
}

int maxidx(int x) {
	return idx[0][x] > idx[1][x] ? (idx[0][x] > idx[2][x] ? idx[0][x] : idx[2][x]) : (idx[1][x] > idx[2][x] ? idx[1][x] : idx[2][x]);
}

int findzero(int x, int idx, int l, int r) {
	if (l == r) return seg[idx] + lazy[idx] == 0 ? l : l - 1;
	seg[idx] += lazy[idx];
	lazy[idx * 2] += lazy[idx];
	lazy[idx * 2 + 1] += lazy[idx];
	lazy[idx] = 0;
	int m = (l + r) / 2;
	if (x <= m) return findzero(x, idx * 2, l, m);
	int t = findzero(x, idx * 2 + 1, m + 1, r);
	return t == m ? findzero(x, idx * 2, l, m) : t;
}

void updseg(int a, int b, int c, int idx, int l, int r) {
	//printf("(%d %d %d %d)\n", l, r, seg[idx], lazy[idx]);
	if (a > b) return;
	if (a <= l && r <= b)  lazy[idx] += c;
	else if (a <= r && l <= b) {
		int m = (l + r) / 2;
		updseg(a, b, c, idx * 2, l, m);
		updseg(a, b, c, idx * 2 + 1, m + 1, r);
		seg[idx] = seg[idx * 2] < seg[idx * 2 + 1] ? seg[idx * 2] : seg[idx * 2 + 1];
	}
	seg[idx] += lazy[idx];
	lazy[idx * 2] += lazy[idx];
	lazy[idx * 2 + 1] += lazy[idx];
	lazy[idx] = 0;
}

int main() {
	int T[MAXN], X[MAXN], P[MAXN], A[MAXN], B[MAXN];

	//freopen("input.txt", "r", stdin);

	scanf("%d%d", &N, &Q);
	for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) scanf("%d", &r[i][j]);
	for (int i = 0; i < Q; i++) {
		scanf("%d", T + i);
		if (T[i] == 1) scanf("%d", X + i);
		else scanf("%d%d%d", P + i, A + i, B + i);
	}

	for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) idx[i][r[i][j]] = j;
	//for (int i = 1; i <= N; i++) printf("[%d %d]\n", minidx(i), maxidx(i));
	for (int i = 1; i <= N; i++) {
		updseg(minidx(i) + 1, maxidx(i), 1, 1, 0, N - 1);
		//for (int j = 1; j < 2 * N; j ++) printf("%d %d\n", seg[j], lazy[j]);
		//printf("##\n");
	}
	
	for (int i = 0; i < Q; i++) {
		//for (int j = 1; j < 2 * N; j++) printf("%d %d\n", seg[j], lazy[j]);
		//printf("*\n");
		if (T[i] == 1) {
			if(findzero(idx[0][X[i]], 1, 0, N-1)==0) printf("DA\n");
			else printf("NE\n");
		}
		else {
			updseg(minidx(A[i]) + 1, maxidx(A[i]), -1, 1, 0, N - 1);
			updseg(minidx(B[i]) + 1, maxidx(B[i]), -1, 1, 0, N - 1);
			//printf("@@@%d %d\n", idx[P[i]][A[i]], idx[P[i]][B[i]]);
			swap(idx[P[i]-1][A[i]], idx[P[i]-1][B[i]]);
			//for (int j = 1; j < 2 * N; j++) printf("%d %d\n", seg[j], lazy[j]);
			//printf("%d %d %d %d\n", minidx(A[i]), maxidx(A[i]), minidx(B[i]), maxidx(B[i]));
			//printf("%d %d\n", idx[P[i]][A[i]], idx[P[i]][B[i]]);
			updseg(minidx(A[i]) + 1, maxidx(A[i]), 1, 1, 0, N - 1);
			updseg(minidx(B[i]) + 1, maxidx(B[i]), 1, 1, 0, N - 1);
		}
	}

	return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:56:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) scanf("%d", &r[i][j]);
                                                          ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", T + i);
   ~~~~~^~~~~~~~~~~~~
tenis.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (T[i] == 1) scanf("%d", X + i);
                  ~~~~~^~~~~~~~~~~~~
tenis.cpp:60:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d%d%d", P + i, A + i, B + i);
        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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