oj.uz

답안 #157821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157821 2019-10-13T08:03:35 Z imyujin Tenis (COI19_tenis) C++17
28 / 100
 86 ms 8440 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int MAXN = 100010;
const int MX = 1 << 17;

int N, Q;
int A[3][MAXN];
int idx[3][MAXN];
lint s[MAXN];
lint seg[2 * MX], lazy[2 * MX];

void mkseg(int idx, int l, int r) {
	if(l == r) seg[idx] = s[l] - (lint)l * (l + 1);
	else {
		int m = (l + r) / 2;
		mkseg(idx * 2, l, m);
		mkseg(idx * 2 + 1, m + 1, r);
		seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

void spreadlazy(int idx) {
	seg[idx * 2] += lazy[idx];
	seg[idx * 2 + 1] += lazy[idx];
	lazy[idx * 2] += lazy[idx];
	lazy[idx * 2 + 1] += lazy[idx];
	lazy[idx] = 0;
}

int gseg(int idx, int l, int r) {
	if(seg[idx] > 0) return -1;
	if(l == r) return l;
	int m = (l + r) / 2;
	spreadlazy(idx);
	int t = gseg(idx * 2, l, m);
	return t == -1 ? gseg(idx * 2 + 1, m + 1, r) : t;
}

void updseg(int idx, int l, int r, int x, int z) {
	if(x <= l) {
		seg[idx] += z;
		lazy[idx] += z;
	}
	else if(x <= r) {
		int m = (l + r) / 2;
		updseg(idx * 2, l, m, x, z);
		updseg(idx * 2 + 1, m + 1, r, x, z);
	}
}
void updseg(int x, int z) { updseg(1, 0, N - 1, x, z); }

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) cin >> A[i][j];

	for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) idx[i][A[i][j]] = j;
	for(int i = 0; i < N; i++) 
		s[i] = (i > 0 ? s[i - 1] : 0) + idx[0][A[1][i]] + idx[0][A[2][i]];
	mkseg(1, 0, N - 1);

	while(Q--) {
		int c;
		cin >> c;
		if(c == 1) {
			int x;
			cin >> x;
			int t = gseg(1, 0, N - 1);
			cout << (idx[0][x] <= t ? "DA" : "NE") << "\n";
		}
		else {
			int p, a, b;
			cin >> p >> a >> b;
			p--;
			if(p == 0) {
				for(int i = 1; i < 3; i++) {
					updseg(idx[i][a], idx[0][b] - idx[0][a]);
					updseg(idx[i][b], idx[0][a] - idx[0][b]);
				}
				swap(idx[0][a], idx[0][b]);
			}
			else {
				updseg(idx[p][a], idx[0][b] - idx[0][a]);
				updseg(idx[p][b], idx[0][a] - idx[0][b]);
				swap(idx[p][a], idx[p][b]);
			}
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Incorrect 2 ms 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Incorrect 2 ms 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 8440 KB Output is correct
2 Correct 79 ms 8316 KB Output is correct
3 Correct 77 ms 8312 KB Output is correct
4 Correct 83 ms 8312 KB Output is correct
5 Correct 75 ms 8412 KB Output is correct
6 Correct 86 ms 8292 KB Output is correct
7 Correct 75 ms 8388 KB Output is correct
8 Correct 86 ms 8312 KB Output is correct
9 Correct 74 ms 8420 KB Output is correct
10 Correct 76 ms 8328 KB Output is correct
11 Correct 73 ms 8440 KB Output is correct
12 Correct 77 ms 8312 KB Output is correct
13 Correct 86 ms 8380 KB Output is correct
14 Correct 75 ms 8312 KB Output is correct
15 Correct 75 ms 8284 KB Output is correct

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Incorrect 2 ms 504 KB Output isn't correct
9 Halted 0 ms 0 KB -