Submission #234791

#	Time	Username	Problem	Language	Result	Execution time	Memory
234791		Atalasion	Tenis (COI19_tenis)	C++14	100 / 100	282 ms	8060 KiB

tenis

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, q, P[3][N], koj[3][N], seg[N << 2], lazy[N << 2];

void modify(int id, int x){
	seg[id] += x;
	lazy[id] += x;
}

void shift(int id){
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = 0;
}

void add(int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		modify(id, x);
		return;
	}
	int md = (l + r) >> 1;
	shift(id);
	add(id << 1, lq, rq, x,l ,md);
	add(id << 1 | 1, lq, rq, x, md, r);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

int get(int id, int l, int r){
	if (r - l == 1) return l;
	shift(id);
	int md = (l + r )>> 1;
	if (seg[id << 1] == 0) return get(id << 1, l, md);
	return get(id << 1 | 1, md, r);
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 0; i < 3; i++){
		for (int j = 1; j <= n; j++){
			cin >> P[i][j];
			koj[i][P[i][j]] = j;
		}
	}
	for (int i = 1; i <= n; i++){
		add(1, min({koj[0][i], koj[1][i], koj[2][i]}), n + 1, 1, 1, n + 1);
		add(1, max({koj[0][i], koj[1][i], koj[2][i]}), n + 1, -1, 1, n + 1);
	}
	for (int i = 1; i <= q; i++){
		int x;
		cin >> x;
		if (x == 1){
			int c;
			cin >> c;
			int K = get(1, 1, n + 1);
//			cout << K << '\n';
			if (K >= koj[0][c]) cout << "DA\n";
			else cout << "NE\n";
		}else{
			int p, a, b;
			cin >> p >> a >> b;
			p--;
			int x = koj[p][a], y = koj[p][b];
			add(1, min({koj[0][a], koj[1][a], koj[2][a]}), n + 1, -1, 1, n + 1);
			add(1, max({koj[0][a], koj[1][a], koj[2][a]}), n + 1, 1, 1, n + 1);
			add(1, min({koj[0][b], koj[1][b], koj[2][b]}), n + 1, -1, 1, n + 1);
			add(1, max({koj[0][b], koj[1][b], koj[2][b]}), n + 1, 1, 1, n + 1);
			koj[p][a] = y, koj[p][b] = x;
			add(1, min({koj[0][a], koj[1][a], koj[2][a]}), n + 1, +1, 1, n + 1);
			add(1, max({koj[0][a], koj[1][a], koj[2][a]}), n + 1, -1, 1, n + 1);
			add(1, min({koj[0][b], koj[1][b], koj[2][b]}), n + 1, +1, 1, n + 1);
			add(1, max({koj[0][b], koj[1][b], koj[2][b]}), n + 1, -1, 1, n + 1);
		}
	}










	return 0;
}

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