oj.uz

Submission #234922

# Submission time Handle Problem Language Result Execution time Memory
234922 2020-05-26T09:31:21 Z Saboon Tenis (COI19_tenis) C++14
0 / 100
 281 ms 7524 KB 
#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];
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;
	if (seg[2*id+0].first <= seg[2*id+1].first)
		seg[id] = seg[2*id+0];
	else
		seg[id] = 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;
			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);
			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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 281 ms 7524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -