oj.uz

Submission #234999

# Submission time Handle Problem Language Result Execution time Memory
234999 2020-05-26T16:06:59 Z Saboon Tenis (COI19_tenis) C++14
0 / 100
 281 ms 8664 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], 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.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 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 4 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 8664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

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