답안 #75084 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75084	2018-09-08T09:32:24 Z	ics0503	자리 배치 (IOI18_seats)	C++17	100 / 100	3069 ms	153252 KB

seats

#include "seats.h"
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int h, w, n; 
struct ND {int am, as, bm, bs, S, alaz,blaz;}tree[4141414];
int min(int a, int b) { if (a < b)return a; return b; }
int max(int a, int b) { if (a > b)return a; return b; }
void update(int w) {
	int c1 = w << 1, c2 = (w << 1) + 1;
	tree[w].am = min(tree[c1].am, tree[c2].am);
	tree[w].bm = min(tree[c1].bm, tree[c2].bm);
	tree[w].as = tree[w].bs = tree[w].S = 0;
	if (tree[w].am == tree[c1].am)tree[w].as += tree[c1].as;
	if (tree[w].am == tree[c2].am)tree[w].as += tree[c2].as;
	if (tree[w].bm == tree[c1].bm)tree[w].bs += tree[c1].bs;
	if (tree[w].bm == tree[c2].bm)tree[w].bs += tree[c2].bs;
	if (tree[w].am == tree[c1].am && tree[w].bm == tree[c1].bm)tree[w].S += tree[c1].S;
	if (tree[w].am == tree[c2].am && tree[w].bm == tree[c2].bm)tree[w].S += tree[c2].S;
}
void lazy(int w) {
	if (tree[w].alaz == 0 && tree[w].blaz == 0)return;
	int c1 = w << 1, c2 = (w << 1) + 1;
	tree[c1].alaz += tree[w].alaz, tree[c2].alaz += tree[w].alaz;
	tree[c1].blaz += tree[w].blaz, tree[c2].blaz += tree[w].blaz;
	tree[c1].am += tree[w].alaz; tree[c2].am += tree[w].alaz;
	tree[c1].bm += tree[w].blaz; tree[c2].bm += tree[w].blaz;
	tree[w].alaz = tree[w].blaz = 0;
}
void insert_g(int w, int s, int e, int l, int r, int tp, int g) {
	if (s != e)lazy(w);
	if (s == l&&e == r) {
		if (tp == 0) {
			tree[w].alaz += g;
			tree[w].am += g;
		}
		else{
			tree[w].blaz += g;
			tree[w].bm += g;
		}
		return;
	}
	int m = (s + e) >> 1;
	if (l <= m)insert_g(w * 2, s, m, l, min(m, r), tp, g);
	if (m + 1 <= r)insert_g(w * 2 + 1, m + 1, e, max(m + 1, l), r, tp, g);
	update(w);
}
int x[1212121], y[1212121];
vector<int>M[1212121];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int A[1212121], B[1212121];

void init(int w, int s, int e) {
	if (s == e) { tree[w].am = A[s], tree[w].bm = B[s], tree[w].S = tree[w].as = tree[w].bs = 1; return; }
	int m = (s + e) >> 1;
	init(w * 2, s, m);
	init(w * 2 + 1, m + 1, e);
	update(w);
}
int AT[1212121], BT[1212121];
void go_1(int x, int y, int g, int tp = 0) {
	int i;
	for (i = 0; i < 4; i++) {
		int ni = (i + 1) % 4;
		int nx = x + dx[i], ny = y + dy[i];
		int nnx = x + dx[ni], nny = y + dy[ni];
		int si, ei;
		si = M[x][y], ei = min(M[nx][ny], M[nnx][nny]) - 1;
		if (si <= ei) {
			if (tp == 0)insert_g(1, 1, n, si, ei, 0, g);
			else AT[si] += g, AT[ei + 1] -= g;
		}
		si = max(M[nx][ny], M[nnx][nny]), ei = M[x][y] - 1;
		if (si <= ei) {
			if(tp==0)insert_g(1, 1, n, si, ei, 1, g);
			else BT[si] += g, BT[ei + 1] -= g;
		}
	}
}
void go_2(int x, int y,int rx,int ry, int g) {
	int i;
	for (i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx == rx&&ny == ry)continue;
		int ni, nnx, nny, si, ei;
		ni = (i + 1) % 4;
		nnx = nx + dx[ni], nny = ny + dy[ni];
		si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1;
		if (si <= ei)insert_g(1, 1, n, si, ei, 0, g);
		si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1;
		if (si <= ei)insert_g(1, 1, n, si, ei, 1, g);
		ni = (i + 3) % 4;
		nnx = nx + dx[ni], nny = ny + dy[ni];
		si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1;
		if (si <= ei)insert_g(1, 1, n, si, ei, 0, g);
		si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1;
		if (si <= ei)insert_g(1, 1, n, si, ei, 1, g);
	}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	int i, j;
	h = H, w = W; n = H*W;
	for (i = 0; i <= h + 1; i++) for (j = 0; j <= w + 1; j++)M[i].push_back(n + 1);
	for (i = 0; i < n; i++)x[i + 1] = R[i] + 1, y[i + 1] = C[i] + 1;
	for (i = 1; i <= n; i++) M[x[i]][y[i]] = i;
	for (i = 1; i <= h; i++) for (j = 1; j <= w; j++) go_1(i, j, 1, 1);
	for (i = 1; i <= n; i++)A[i] = A[i - 1] + AT[i], B[i] = B[i - 1] + BT[i];
	init(1, 1, n);
}
void swap(int &a, int &b) { int c = a; a = b; b = c; }
int swap_seats(int a, int b) {
	a++, b++;
	go_1(x[a], y[a], -1); go_2(x[a], y[a], x[b], y[b], -1);
	go_1(x[b], y[b], -1); go_2(x[b], y[b], x[a], y[a], -1);
	swap(x[a], x[b]), swap(y[a], y[b]);
	swap(M[x[a]][y[a]], M[x[b]][y[b]]);
	go_1(x[a], y[a], 1); go_2(x[a], y[a], x[b], y[b], 1);
	go_1(x[b], y[b], 1); go_2(x[b], y[b], x[a], y[a], 1);
	return tree[1].S;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	28920 KB	Output is correct
2	Correct	56 ms	28920 KB	Output is correct
3	Correct	85 ms	29208 KB	Output is correct
4	Correct	59 ms	29208 KB	Output is correct
5	Correct	51 ms	29208 KB	Output is correct
6	Correct	79 ms	29208 KB	Output is correct
7	Correct	82 ms	29208 KB	Output is correct
8	Correct	72 ms	29208 KB	Output is correct
9	Correct	72 ms	29300 KB	Output is correct
10	Correct	82 ms	29300 KB	Output is correct
11	Correct	78 ms	29300 KB	Output is correct
12	Correct	52 ms	29300 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	28920 KB	Output is correct
2	Correct	56 ms	28920 KB	Output is correct
3	Correct	85 ms	29208 KB	Output is correct
4	Correct	59 ms	29208 KB	Output is correct
5	Correct	51 ms	29208 KB	Output is correct
6	Correct	79 ms	29208 KB	Output is correct
7	Correct	82 ms	29208 KB	Output is correct
8	Correct	72 ms	29208 KB	Output is correct
9	Correct	72 ms	29300 KB	Output is correct
10	Correct	82 ms	29300 KB	Output is correct
11	Correct	78 ms	29300 KB	Output is correct
12	Correct	52 ms	29300 KB	Output is correct
13	Correct	154 ms	30612 KB	Output is correct
14	Correct	170 ms	30612 KB	Output is correct
15	Correct	96 ms	30624 KB	Output is correct
16	Correct	78 ms	30752 KB	Output is correct
17	Correct	120 ms	30752 KB	Output is correct
18	Correct	111 ms	30752 KB	Output is correct
19	Correct	107 ms	30752 KB	Output is correct
20	Correct	94 ms	30752 KB	Output is correct
21	Correct	78 ms	30752 KB	Output is correct
22	Correct	78 ms	30780 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	761 ms	129852 KB	Output is correct
2	Correct	595 ms	129980 KB	Output is correct
3	Correct	567 ms	129980 KB	Output is correct
4	Correct	590 ms	129980 KB	Output is correct
5	Correct	593 ms	129980 KB	Output is correct
6	Correct	579 ms	129980 KB	Output is correct
7	Correct	571 ms	129980 KB	Output is correct
8	Correct	651 ms	129980 KB	Output is correct
9	Correct	625 ms	129980 KB	Output is correct
10	Correct	585 ms	129980 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	149 ms	129980 KB	Output is correct
2	Correct	194 ms	129980 KB	Output is correct
3	Correct	576 ms	129980 KB	Output is correct
4	Correct	802 ms	129980 KB	Output is correct
5	Correct	530 ms	133720 KB	Output is correct
6	Correct	945 ms	153252 KB	Output is correct
7	Correct	602 ms	153252 KB	Output is correct
8	Correct	603 ms	153252 KB	Output is correct
9	Correct	573 ms	153252 KB	Output is correct
10	Correct	654 ms	153252 KB	Output is correct
11	Correct	632 ms	153252 KB	Output is correct

Subtask #5
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	153252 KB	Output is correct
2	Correct	170 ms	153252 KB	Output is correct
3	Correct	303 ms	153252 KB	Output is correct
4	Correct	390 ms	153252 KB	Output is correct
5	Correct	732 ms	153252 KB	Output is correct
6	Correct	1345 ms	153252 KB	Output is correct
7	Correct	1361 ms	153252 KB	Output is correct
8	Correct	1308 ms	153252 KB	Output is correct
9	Correct	1804 ms	153252 KB	Output is correct
10	Correct	1194 ms	153252 KB	Output is correct
11	Correct	1199 ms	153252 KB	Output is correct
12	Correct	1249 ms	153252 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	28920 KB	Output is correct
2	Correct	56 ms	28920 KB	Output is correct
3	Correct	85 ms	29208 KB	Output is correct
4	Correct	59 ms	29208 KB	Output is correct
5	Correct	51 ms	29208 KB	Output is correct
6	Correct	79 ms	29208 KB	Output is correct
7	Correct	82 ms	29208 KB	Output is correct
8	Correct	72 ms	29208 KB	Output is correct
9	Correct	72 ms	29300 KB	Output is correct
10	Correct	82 ms	29300 KB	Output is correct
11	Correct	78 ms	29300 KB	Output is correct
12	Correct	52 ms	29300 KB	Output is correct
13	Correct	154 ms	30612 KB	Output is correct
14	Correct	170 ms	30612 KB	Output is correct
15	Correct	96 ms	30624 KB	Output is correct
16	Correct	78 ms	30752 KB	Output is correct
17	Correct	120 ms	30752 KB	Output is correct
18	Correct	111 ms	30752 KB	Output is correct
19	Correct	107 ms	30752 KB	Output is correct
20	Correct	94 ms	30752 KB	Output is correct
21	Correct	78 ms	30752 KB	Output is correct
22	Correct	78 ms	30780 KB	Output is correct
23	Correct	761 ms	129852 KB	Output is correct
24	Correct	595 ms	129980 KB	Output is correct
25	Correct	567 ms	129980 KB	Output is correct
26	Correct	590 ms	129980 KB	Output is correct
27	Correct	593 ms	129980 KB	Output is correct
28	Correct	579 ms	129980 KB	Output is correct
29	Correct	571 ms	129980 KB	Output is correct
30	Correct	651 ms	129980 KB	Output is correct
31	Correct	625 ms	129980 KB	Output is correct
32	Correct	585 ms	129980 KB	Output is correct
33	Correct	149 ms	129980 KB	Output is correct
34	Correct	194 ms	129980 KB	Output is correct
35	Correct	576 ms	129980 KB	Output is correct
36	Correct	802 ms	129980 KB	Output is correct
37	Correct	530 ms	133720 KB	Output is correct
38	Correct	945 ms	153252 KB	Output is correct
39	Correct	602 ms	153252 KB	Output is correct
40	Correct	603 ms	153252 KB	Output is correct
41	Correct	573 ms	153252 KB	Output is correct
42	Correct	654 ms	153252 KB	Output is correct
43	Correct	632 ms	153252 KB	Output is correct
44	Correct	89 ms	153252 KB	Output is correct
45	Correct	170 ms	153252 KB	Output is correct
46	Correct	303 ms	153252 KB	Output is correct
47	Correct	390 ms	153252 KB	Output is correct
48	Correct	732 ms	153252 KB	Output is correct
49	Correct	1345 ms	153252 KB	Output is correct
50	Correct	1361 ms	153252 KB	Output is correct
51	Correct	1308 ms	153252 KB	Output is correct
52	Correct	1804 ms	153252 KB	Output is correct
53	Correct	1194 ms	153252 KB	Output is correct
54	Correct	1199 ms	153252 KB	Output is correct
55	Correct	1249 ms	153252 KB	Output is correct
56	Correct	233 ms	153252 KB	Output is correct
57	Correct	626 ms	153252 KB	Output is correct
58	Correct	907 ms	153252 KB	Output is correct
59	Correct	2094 ms	153252 KB	Output is correct
60	Correct	3069 ms	153252 KB	Output is correct
61	Correct	1828 ms	153252 KB	Output is correct
62	Correct	1427 ms	153252 KB	Output is correct
63	Correct	2669 ms	153252 KB	Output is correct
64	Correct	2056 ms	153252 KB	Output is correct
65	Correct	1794 ms	153252 KB	Output is correct
66	Correct	2169 ms	153252 KB	Output is correct
67	Correct	1984 ms	153252 KB	Output is correct
68	Correct	1630 ms	153252 KB	Output is correct
69	Correct	2798 ms	153252 KB	Output is correct

답안 #75084

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 6.0 / 6.0

Subtask #3 20.0 / 20.0

Subtask #4 6.0 / 6.0

Subtask #5 33.0 / 33.0

Subtask #6 30.0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
6.0 / 6.0

Subtask #3
20.0 / 20.0

Subtask #4
6.0 / 6.0

Subtask #5
33.0 / 33.0

Subtask #6
30.0 / 30.0