Submission #234999

#	Time	Username	Problem	Language	Result	Execution time	Memory
234999		Saboon	Tenis (COI19_tenis)	C++14	0 / 100	281 ms	8664 KiB

tenis

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;
 
const int maxn = 1e5 + 10;
 
int a[4][maxn], b[4][maxn];
pair<int,int> seg[4*maxn];
int lazy[4*maxn];
 
void add(int id, int L, int R, int l, int r, int val){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id].first += val;
		lazy[id] += val;
		return;
	}
	int mid = (L + R) >> 1;
	add(2*id+0, L, mid, l, r, val + lazy[id]);
	add(2*id+1, mid, R, l, r, val + lazy[id]);
	lazy[id] = 0;
	seg[id] = min(seg[2*id+0], seg[2*id+1]);
}
 
void build(int id, int L, int R){
	seg[id].second = L;
	if (L + 1 == R)
		return;
	int mid = (L + R) >> 1;
	build(2*id+0, L, mid);
	build(2*id+1, mid, R);
}
 
int getmax(int idx){
	int ret = 1;
	for (int i = 1; i <= 3; i++)
		ret = max(ret, a[i][idx]);
	return ret;
}
 
int getmin(int idx){
	int ret = maxn;
	for (int i = 1; i <= 3; i++)
		ret = min(ret, a[i][idx]);
	return ret;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	for (int j = 1; j <= 3; j++)
		for (int i = 1; i <= n; i++){
			int x;
			cin >> x;
			b[j][i] = x;
			a[j][x] = i;
		}
	build(1, 1, n+2);
	for (int i = 1; i <= n; i++){
		int l = getmin(i), r = getmax(i);
		add(1, 1, n+2, l, r, +1);
	}
	for (int i = 1; i <= q; i++){
		int type;
		cin >> type;
		if (type == 1){
			int idx;
			cin >> idx;
			int l = getmin(idx);
			if (l <= seg[1].second)
				cout << "DA\n";
			else
				cout << "NE\n";
		}
		else{
			int p, A, B;
			cin >> p >> A >> B;
			int l = getmin(A), r = getmax(A);
			add(1, 1, n+2, l, r, -1);
				l = getmin(B), r = getmax(B);
			add(1, 1, n+2, l, r, -1);
			b[p][a[p][A]] = A;
			b[p][a[p][B]] = B;
			swap(a[p][A], a[p][B]);
				l = getmin(A), r = getmax(A);
			add(1, 1, n+2, l, r, +1);
				l = getmin(B), r = getmax(B);
			add(1, 1, n+2, l, r, +1);
		}
	}
}

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