제출 #234712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234712		amoo_safar	Tenis (COI19_tenis)	C++14	100 / 100	275 ms	8952 KiB

tenis

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, p[4][N], ind[4][N];

int lz[N << 2];
pii seg[N << 2];
void Build(int id, int L, int R){
	if(L + 1 == R){
		seg[id] = {0, L};
		return ;
	}
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	seg[id].F += lz[id];
}
void Add(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		lz[id] += x; seg[id].F += x;
		return ;
	}
	int mid = (L + R) >> 1;
	Add(id << 1, l, r, x, L, mid);
	Add(id << 1 | 1, l, r, x, mid, R);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	seg[id].F += lz[id];
}

void Apply(int x, int d){
	int l = min({ind[1][x], ind[2][x], ind[3][x]});
	int r = max({ind[1][x], ind[2][x], ind[3][x]});
	Add(1, l, r, d, 1, n + 1);
	//cerr << "! " << l << ' ' << r << ' ' << d << '\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q;
	cin >> n >> q;
	for(int k = 1; k <= 3; k++) for(int i = 1; i <= n; i++){
		cin >> p[k][i];
		ind[k][p[k][i]] = i;
	}
	Build(1, 1, n + 1);
	for(int i = 1; i <= n; i++) Apply(i, 1);
	int t, x, a, b, P;
	for(int i = 0; i < q; i++){
		//cerr << seg[1].F << ' ' << seg[1].S << '\n';
		cin >> t;
		if(t == 1){
			cin >> x;
			cout << (min({ind[1][x], ind[2][x], ind[3][x]}) <= seg[1].S ? "DA" : "NE") << '\n';
		} else {
			cin >> P >> a >> b;
			Apply(a, -1);
			Apply(b, -1);
			p[P][ind[P][a]] = b;
			p[P][ind[P][b]] = a;
			swap(ind[P][a], ind[P][b]);
			Apply(a, 1);
			Apply(b, 1);	
		}
	}
	return 0;
}

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