Submission #208385

#	Time	Username	Problem	Language	Result	Execution time	Memory
208385		bensonlzl	Tenis (COI19_tenis)	C++14	100 / 100	172 ms	14900 KiB

tenis

#include <bits/stdc++.h>

using namespace std;

int N, Q, R1[100005], R2[100005], R3[100005], M[100005], X, P, A, B, k;

int maxiR(int x){
	return max(R1[x],max(R2[x],R3[x]));
}

int val[100005];

struct node{
	node *left, *right;
	int m = 1e9, mdex, S, E, lazy;
	
	node(int _s, int _e){
		S = _s, E = _e;
		if (S == E){
			m = val[S];
			mdex = S;
			return;
		}
		left = new node(S,(S+E)/2);
		right = new node((S+E)/2+1,E);
		if (left->m < right->m){
			mdex = left->mdex;
			m = left->m;
		}
		else{
			m = right->m;
			mdex = right->mdex;
		}
	}
	
	void propagate(){
		if (lazy){
			left->m += lazy;
			right->m += lazy;
			left->lazy += lazy;
			right->lazy += lazy;
			lazy = 0;
		}
	}
	
	void update(int l, int r, int v){
		if (l > r) return;
		if (l > E || r < S) return;
		if (l <= S && E <= r){
			lazy += v;
			m += v;
			return;
		}
		propagate();
		left->update(l,r,v);
		right->update(l,r,v);
		if (left->m < right->m){
			mdex = left->mdex;
			m = left->m;
		}
		else{
			m = right->m;
			mdex = right->mdex;
		}
	}
	
}*root;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> Q;
	int x;
	for (int i = N; i >= 1; --i){
		cin >> x;
		R1[x] = i;
	}
	for (int i = N; i >= 1; --i){
		cin >> x;
		R2[x] = i;
	}
	for (int i = N; i >= 1; --i){
		cin >> x;
		R3[x] = i;
	}
	
	for (int i = 1; i <= N; ++i){
		M[i] = maxiR(i);
		val[M[i]]++;
	}
	
	for (int i = 1; i <= N; ++i){
		val[i] += val[i-1];
	}
	
	for (int i = 1; i <= N; ++i){
		val[i] = i-val[i];
	}
	
	root = new node(1,N-1);
	
	for (int i = 1; i <= Q; ++i){
		cin >> k;
		if (k == 1){
			cin >> X;
			if (maxiR(X) > root->mdex || root->m > 0){
				cout << "DA\n";
			}
			else cout << "NE\n";
		}
		if (k == 2){
			cin >> P >> A >> B;
			int oldA = maxiR(A), oldB = maxiR(B);
			
			int t;
			if (P == 1){
				t = R1[A];
				R1[A] = R1[B];
				R1[B] = t;
			}
			if (P == 2){
				t = R2[A];
				R2[A] = R2[B];
				R2[B] = t;
			}
			if (P == 3){
				t = R3[A];
				R3[A] = R3[B];
				R3[B] = t;
			}
			
			root->update(oldA,N-1,1);
			root->update(oldB,N-1,1);
			root->update(maxiR(A),N-1,-1);
			root->update(maxiR(B),N-1,-1);
		}
	}
}

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