Submission #157823

#	Time	Username	Problem	Language	Result	Execution time	Memory
157823		imyujin	Tenis (COI19_tenis)	C++17	100 / 100	138 ms	10700 KiB

tenis

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int MAXN = 100010;
const int MX = 1 << 17;

int N, Q;
int A[3][MAXN];
int idx[3][MAXN];
lint s[MAXN];
lint seg[2 * MX], lazy[2 * MX];

void mkseg(int idx, int l, int r) {
	if(l == r) seg[idx] = s[l] - (lint)l * (l + 1);
	else {
		int m = (l + r) / 2;
		mkseg(idx * 2, l, m);
		mkseg(idx * 2 + 1, m + 1, r);
		seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

void spreadlazy(int idx) {
	seg[idx * 2] += lazy[idx];
	seg[idx * 2 + 1] += lazy[idx];
	lazy[idx * 2] += lazy[idx];
	lazy[idx * 2 + 1] += lazy[idx];
	lazy[idx] = 0;
}

int gseg(int idx, int l, int r) {
	if(seg[idx] > 0) return -1;
	if(l == r) return l;
	int m = (l + r) / 2;
	spreadlazy(idx);
	int t = gseg(idx * 2, l, m);
	return t == -1 ? gseg(idx * 2 + 1, m + 1, r) : t;
}

void updseg(int idx, int l, int r, int x, int z) {
	if(x <= l) {
		seg[idx] += z;
		lazy[idx] += z;
	}
	else if(x <= r) {
		int m = (l + r) / 2;
		updseg(idx * 2, l, m, x, z);
		updseg(idx * 2 + 1, m + 1, r, x, z);
		seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]) + lazy[idx];
	}
}
void updseg(int x, int z) { updseg(1, 0, N - 1, x, z); }

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) cin >> A[i][j];

	for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) idx[i][A[i][j]] = j;
	for(int i = 0; i < N; i++) 
		s[i] = (i > 0 ? s[i - 1] : 0) + idx[0][A[1][i]] + idx[0][A[2][i]];
	mkseg(1, 0, N - 1);

	while(Q--) {
		int c;
		cin >> c;
		if(c == 1) {
			int x;
			cin >> x;
			cout << (idx[0][x] <= gseg(1, 0, N - 1) ? "DA" : "NE") << "\n";
		}
		else {
			int p, a, b;
			cin >> p >> a >> b;
			if(--p == 0) {
				for(int i = 1; i < 3; i++) {
					updseg(idx[i][a], idx[0][b] - idx[0][a]);
					updseg(idx[i][b], idx[0][a] - idx[0][b]);
				}
				swap(idx[0][a], idx[0][b]);
			}
			else {
				updseg(idx[p][a], idx[0][b] - idx[0][a]);
				updseg(idx[p][b], idx[0][a] - idx[0][b]);
				swap(idx[p][a], idx[p][b]);
			}
		}
	}
	return 0;
}

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