oj.uz

답안 #170277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170277 2019-12-24T12:47:32 Z socho 자리 배치 (IOI18_seats) C++14
11 / 100
 4000 ms 228856 KB 
#include "bits/stdc++.h"
#include "seats.h"
using namespace std;

struct node_co {
	
	int seg_st, seg_en, seg_mid;
	int valmax, valmin;
	node_co *left, *right;
	
	node_co(int st, int en) {
		seg_st = st;
		seg_en = en;
		int mi = (st + en) / 2;
		seg_mid = mi;
		valmax = valmin = 0;
		if (st == en) return;
		left = new node_co(st, mi);
		right = new node_co(mi+1, en);
	}
	
	void update(int pos, int to) {
		if (pos > seg_en || pos < seg_st) {
			return;
		}
		if (seg_st == seg_en) {
			valmax = to;
			valmin = to;
			return;
		}
		left->update(pos, to);
		right->update(pos, to);
		valmax = max(left->valmax, right->valmax);
		valmin = min(left->valmin, right->valmin);
	}
	
	pair<int, int> query(int a, int b) {
		if (a > seg_en || b < seg_st) return make_pair(INT_MIN, INT_MAX);
		if (a <= seg_st && b >= seg_en) {
			return make_pair(valmax, valmin);
		}
		pair<int, int> le = left->query(a, b);
		pair<int, int> ri = right->query(a, b);
		return make_pair(max(le.first, ri.first), min(le.second, ri.second));
	}
	
} *hno, *vno;

const int MXN = 1000005;
int h, w, n;

int hat[MXN], vat[MXN];
bool work[MXN];
int counter = 0;

void valid(int c) {
	pair<int, int> h = hno->query(0, c);
	pair<int, int> v = vno->query(0, c);
	int hdif = h.first - h.second + 1;
	int vdif = v.first - v.second + 1;
	bool ans = false;
	if (c + 1 == (hdif * vdif)) {
		ans = true;
	}
	// cout << " > " << c << ' ' << ans << ' ' << h.first << ' ' << h.second << ' ' << v.first << ' ' << v.second << endl;
	if (ans == work[c]) return;
	if (ans) counter++;
	else counter--;
	work[c] = ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	
	h = H;
	w = W;
	n = (h * w);
	
	hno = new node_co(0, n-1);
	vno = new node_co(0, n-1);
	
	for (int i=0; i<n; i++) {
		hat[i] = R[i];
		vat[i] = C[i];
		// cout << i << ' ' << R[i] << ' ' << C[i] << endl;
		hno->update(i, R[i]);
		vno->update(i, C[i]);
	}
	
	memset(work, 0, sizeof work);
	counter = 0;
	for (int i=0; i<n; i++) {
		valid(i);
	}
	
}

int swap_seats(int a, int b) {
	int ax = hat[a], ay = vat[a];
	int bx = hat[b], by = vat[b];
	hat[b] = ax, vat[b] = ay;
	hat[a] = bx, vat[a] = by;
	hno->update(a, hat[a]);
	hno->update(b, hat[b]);
	vno->update(a, vat[a]);
	vno->update(b, vat[b]);
	for (int i=min(a, b); i<=max(a, b); i++) {
		valid(i);
	}
	return counter;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 15 ms 1528 KB Output is correct
4 Correct 15 ms 1528 KB Output is correct
5 Correct 15 ms 1528 KB Output is correct
6 Correct 15 ms 1528 KB Output is correct
7 Correct 15 ms 1528 KB Output is correct
8 Correct 14 ms 1528 KB Output is correct
9 Correct 15 ms 1564 KB Output is correct
10 Correct 15 ms 1532 KB Output is correct
11 Correct 15 ms 1528 KB Output is correct
12 Correct 16 ms 1532 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 15 ms 1528 KB Output is correct
4 Correct 15 ms 1528 KB Output is correct
5 Correct 15 ms 1528 KB Output is correct
6 Correct 15 ms 1528 KB Output is correct
7 Correct 15 ms 1528 KB Output is correct
8 Correct 14 ms 1528 KB Output is correct
9 Correct 15 ms 1564 KB Output is correct
10 Correct 15 ms 1532 KB Output is correct
11 Correct 15 ms 1528 KB Output is correct
12 Correct 16 ms 1532 KB Output is correct
13 Correct 2910 ms 3704 KB Output is correct
14 Correct 2884 ms 3704 KB Output is correct
15 Correct 2860 ms 3688 KB Output is correct
16 Correct 2842 ms 3704 KB Output is correct
17 Correct 2844 ms 3704 KB Output is correct
18 Correct 2847 ms 3680 KB Output is correct
19 Correct 2920 ms 3680 KB Output is correct
20 Correct 3007 ms 3704 KB Output is correct
21 Correct 2987 ms 3704 KB Output is correct
22 Correct 2930 ms 3704 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4045 ms 228856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4014 ms 3448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2420 KB Output is correct
2 Correct 33 ms 2420 KB Output is correct
3 Correct 126 ms 2420 KB Output is correct
4 Correct 2297 ms 2784 KB Output is correct
5 Execution timed out 4022 ms 4600 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 15 ms 1528 KB Output is correct
4 Correct 15 ms 1528 KB Output is correct
5 Correct 15 ms 1528 KB Output is correct
6 Correct 15 ms 1528 KB Output is correct
7 Correct 15 ms 1528 KB Output is correct
8 Correct 14 ms 1528 KB Output is correct
9 Correct 15 ms 1564 KB Output is correct
10 Correct 15 ms 1532 KB Output is correct
11 Correct 15 ms 1528 KB Output is correct
12 Correct 16 ms 1532 KB Output is correct
13 Correct 2910 ms 3704 KB Output is correct
14 Correct 2884 ms 3704 KB Output is correct
15 Correct 2860 ms 3688 KB Output is correct
16 Correct 2842 ms 3704 KB Output is correct
17 Correct 2844 ms 3704 KB Output is correct
18 Correct 2847 ms 3680 KB Output is correct
19 Correct 2920 ms 3680 KB Output is correct
20 Correct 3007 ms 3704 KB Output is correct
21 Correct 2987 ms 3704 KB Output is correct
22 Correct 2930 ms 3704 KB Output is correct
23 Execution timed out 4045 ms 228856 KB Time limit exceeded
24 Halted 0 ms 0 KB -