oj.uz

답안 #868970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868970 2023-11-02T16:42:19 Z serifefedartar Tenis (COI19_tenis) C++17
0 / 100
 61 ms 6436 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+7;
const ll LOGN = 30; 
const ll MAXN = 1e5 + 100;
const ll MULT = 1e9;

int rankV[3][MAXN];
int sg[4*MAXN], lazy[4*MAXN];
void init(int k, int a, int b) {
	if (a == b) {
		sg[k] = a;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

void push(int k, int a, int b) {
	sg[k] += lazy[k];
	if (a != b) {
		lazy[2*k] += lazy[k];
		lazy[2*k+1] += lazy[k];
	}
	lazy[k] = 0;
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
	push(k, a, b);
	if (q_r < a || q_l > b)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] += val;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, val);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b) {
	push(k, a, b);
	if (a == b) {
		return a;
	}
	if (sg[2*k] == 0)
		return query(2*k, a, (a+b)/2);
	return query(2*k+1, (a+b)/2+1, b);
}

int maxi(int x, int y, int z) {
	return max(x, max(y, z));
}

int main() {
	fast
	int N, Q;
	cin >> N >> Q;

	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		rankV[0][x] = i;
	}
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		rankV[1][x] = i;
	}
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		rankV[2][x] = i;
	}
	init(1, 1, N);

	for (int i = 1; i <= N; i++)
		update(1, 1, N, maxi(rankV[0][i], rankV[1][i], rankV[2][i]), N, -1);
	while (Q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x; cin >> x;
			if (maxi(rankV[0][x], rankV[1][x], rankV[2][x]) <= query(1, 1, N))
				cout << "DA\n";
			else
				cout << "NE\n";
		} else {
			int p, a, b; cin >> p >> a >> b;
			update(1, 1, N, maxi(rankV[0][a], rankV[1][a], rankV[2][a]), N, 1);
			update(1, 1, N, maxi(rankV[0][b], rankV[1][b], rankV[2][b]), N, 1);
			swap(rankV[p-1][a], rankV[p-1][b]);
			update(1, 1, N, maxi(rankV[0][a], rankV[1][a], rankV[2][a]), N, -1);
			update(1, 1, N, maxi(rankV[0][b], rankV[1][b], rankV[2][b]), N, -1);
		}
	}
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 6436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -