oj.uz

Submission #121287

# Submission time Handle Problem Language Result Execution time Memory
121287 2019-06-26T09:42:27 Z SirCeness Seats (IOI18_seats) C++17
100 / 100
 3587 ms 119292 KB 
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inf 1000000009
using namespace std;
typedef long long ll;

vector<vector<int> > mat;
int tmp[4];
int MX;
int H, W;
vector<int> R;
vector<int> C;
int lazy[4000006];
int minn[4000006];
int countt[4000006];

void stc(int node, int l, int r){
	if (l == r){
		minn[node] = 0;
		countt[node] = 1;
		lazy[node] = 0;
	} else {
		int m = (l+r)/2;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		minn[node] = min(minn[node*2], minn[node*2+1]);
		countt[node] = 0;
		if (minn[node] == minn[node*2]) countt[node] += countt[node*2];
		if (minn[node] == minn[node*2+1]) countt[node] += countt[node*2+1];
		lazy[node] = 0;
	}
}

int get(int node){
	return minn[node] + lazy[node];
}

void push(int node){
	minn[node] += lazy[node];
	lazy[node*2+1] += lazy[node];
	lazy[node*2] += lazy[node];
	lazy[node] = 0;
}

void stu(int node, int l, int r, int sl, int sr, int val){
	if (sl <= l && r <= sr){
		lazy[node] += val;
	} else if (r < sl ||sr < l){
		return;
	} else {
		int m = (l+r)/2;
		push(node);
		stu(node*2, l, m, sl, sr, val);
		stu(node*2+1, m+1, r, sl, sr, val);
		
		minn[node] = min(get(node*2), get(node*2+1));
		countt[node] = 0;
		if (minn[node] == get(node*2)) countt[node] += countt[node*2];
		if (minn[node] == get(node*2+1)) countt[node] += countt[node*2+1];
	}
}

void yap(int i, int j){
	tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
	tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
	tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
	tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
	sort(tmp, tmp+4);
	//cout << "yap: " << tmp[0] << ", " << tmp[1] << ", " << tmp[2] << ", " << tmp[3] << endl;
	if (tmp[0] < tmp[1]) stu(1, 0, MX-1, tmp[0], tmp[1]-1, +1);
	if (tmp[2] < tmp[3]) stu(1, 0, MX-1, tmp[2], tmp[3]-1, +1);
	//if (tmp[0] < tmp[1]) cout << tmp[0] << " - " << tmp[1]-1 << ": +1" << endl;
	//if (tmp[2] < tmp[3]) cout << tmp[2] << " - " << tmp[3]-1 << ": +1" << endl;
}

void boz(int i, int j){
	tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
	tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
	tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
	tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
	sort(tmp, tmp+4);
	if (tmp[0] != -1) stu(1, 0, MX-1, tmp[0], tmp[1]-1, -1);
	if (tmp[2] != -1) stu(1, 0, MX-1, tmp[2], tmp[3]-1, -1);
}

int getnode(int node, int l, int r, int ind){
	if (l == r) return get(node);
	else {
		int m = (l+r)/2;
		push(node);
		if (ind <= m) return getnode(node*2, l, m, ind);
		else return getnode(node*2+1, m+1, r, ind);
	}
}

void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {
	H = HH;
	W = WW;
	R = RR;
	C = CC;
	MX = H*W;
	mat.resize(H);
	for (int i = 0; i < H; i++) mat[i].resize(W);
	for (int i = 0; i < MX; i++){
		mat[R[i]][C[i]] = i;
	}
	
	/*for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			cout << mat[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/
	
	stc(1, 0, MX-1);
	
	for (int i = -1; i < H; i++){
		for (int j = -1; j < W; j++){
			yap(i, j);
		}
	}
	
	/*for (int i = 0; i < MX; i++) cout << getnode(1, 0, MX-1, i) << " ";
	cout << endl;*/
	
}

int swap_seats(int a, int b) {
	int i1 = R[a];
	int j1 = C[a];
	int i2 = R[b];
	int j2 = C[b];
	boz(i1-1, j1-1);
	boz(i1-1, j1);
	boz(i1, j1-1);
	boz(i1, j1);
	boz(i2-1, j2-1);
	boz(i2-1, j2);
	boz(i2, j2-1);
	boz(i2, j2);
	R[a] = i2;
	R[b] = i1;
	C[a] = j2;
	C[b] = j1;
	mat[i1][j1] = b;
	mat[i2][j2] = a;
	yap(i1, j1);
	yap(i1, j1-1);
	yap(i1-1, j1);
	yap(i1-1, j1-1);
	yap(i2, j2);
	yap(i2, j2-1);
	yap(i2-1, j2);
	yap(i2-1, j2-1);
	return countt[1];
}
/*
int main(){
	freopen("stl.gir", "r", stdin);
	
	int h, w;
	cin >> h >> w;
	vector<int> r;
	vector<int> c;
	for (int i = 0; i < h*w; i++){
		int a, b;
		cin >> a >> b;
		r.pb(a);
		c.pb(b);
	}
	give_initial_chart(h, w, r, c);
	int q;
	cin >> q;
	while(q--){
		int a, b;
		cin >> a >> b;
		cout << swap_seats(a, b) << endl;
	}
	
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Output is correct
2 Correct 22 ms 484 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 30 ms 504 KB Output is correct
8 Correct 28 ms 512 KB Output is correct
9 Correct 29 ms 512 KB Output is correct
10 Correct 30 ms 512 KB Output is correct
11 Correct 28 ms 512 KB Output is correct
12 Correct 17 ms 484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Output is correct
2 Correct 22 ms 484 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 30 ms 504 KB Output is correct
8 Correct 28 ms 512 KB Output is correct
9 Correct 29 ms 512 KB Output is correct
10 Correct 30 ms 512 KB Output is correct
11 Correct 28 ms 512 KB Output is correct
12 Correct 17 ms 484 KB Output is correct
13 Correct 75 ms 1076 KB Output is correct
14 Correct 80 ms 1024 KB Output is correct
15 Correct 44 ms 1024 KB Output is correct
16 Correct 35 ms 1536 KB Output is correct
17 Correct 57 ms 1072 KB Output is correct
18 Correct 56 ms 1024 KB Output is correct
19 Correct 53 ms 1024 KB Output is correct
20 Correct 46 ms 1280 KB Output is correct
21 Correct 35 ms 1072 KB Output is correct
22 Correct 37 ms 1656 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2221 ms 52508 KB Output is correct
2 Correct 1130 ms 68452 KB Output is correct
3 Correct 1085 ms 68440 KB Output is correct
4 Correct 986 ms 68532 KB Output is correct
5 Correct 1040 ms 68500 KB Output is correct
6 Correct 962 ms 68472 KB Output is correct
7 Correct 1088 ms 68524 KB Output is correct
8 Correct 1094 ms 68472 KB Output is correct
9 Correct 1096 ms 68600 KB Output is correct
10 Correct 1047 ms 68536 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1024 KB Output is correct
2 Correct 183 ms 6020 KB Output is correct
3 Correct 1016 ms 52600 KB Output is correct
4 Correct 2288 ms 52484 KB Output is correct
5 Correct 847 ms 68668 KB Output is correct
6 Correct 2149 ms 119292 KB Output is correct
7 Correct 980 ms 68468 KB Output is correct
8 Correct 1328 ms 68584 KB Output is correct
9 Correct 1234 ms 68904 KB Output is correct
10 Correct 1175 ms 71828 KB Output is correct
11 Correct 992 ms 92024 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1524 KB Output is correct
2 Correct 102 ms 1396 KB Output is correct
3 Correct 158 ms 1472 KB Output is correct
4 Correct 210 ms 1528 KB Output is correct
5 Correct 327 ms 2164 KB Output is correct
6 Correct 1372 ms 52880 KB Output is correct
7 Correct 1791 ms 69520 KB Output is correct
8 Correct 1458 ms 69644 KB Output is correct
9 Correct 2789 ms 69496 KB Output is correct
10 Correct 1324 ms 69624 KB Output is correct
11 Correct 1331 ms 69368 KB Output is correct
12 Correct 1308 ms 69512 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Output is correct
2 Correct 22 ms 484 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 30 ms 504 KB Output is correct
8 Correct 28 ms 512 KB Output is correct
9 Correct 29 ms 512 KB Output is correct
10 Correct 30 ms 512 KB Output is correct
11 Correct 28 ms 512 KB Output is correct
12 Correct 17 ms 484 KB Output is correct
13 Correct 75 ms 1076 KB Output is correct
14 Correct 80 ms 1024 KB Output is correct
15 Correct 44 ms 1024 KB Output is correct
16 Correct 35 ms 1536 KB Output is correct
17 Correct 57 ms 1072 KB Output is correct
18 Correct 56 ms 1024 KB Output is correct
19 Correct 53 ms 1024 KB Output is correct
20 Correct 46 ms 1280 KB Output is correct
21 Correct 35 ms 1072 KB Output is correct
22 Correct 37 ms 1656 KB Output is correct
23 Correct 2221 ms 52508 KB Output is correct
24 Correct 1130 ms 68452 KB Output is correct
25 Correct 1085 ms 68440 KB Output is correct
26 Correct 986 ms 68532 KB Output is correct
27 Correct 1040 ms 68500 KB Output is correct
28 Correct 962 ms 68472 KB Output is correct
29 Correct 1088 ms 68524 KB Output is correct
30 Correct 1094 ms 68472 KB Output is correct
31 Correct 1096 ms 68600 KB Output is correct
32 Correct 1047 ms 68536 KB Output is correct
33 Correct 66 ms 1024 KB Output is correct
34 Correct 183 ms 6020 KB Output is correct
35 Correct 1016 ms 52600 KB Output is correct
36 Correct 2288 ms 52484 KB Output is correct
37 Correct 847 ms 68668 KB Output is correct
38 Correct 2149 ms 119292 KB Output is correct
39 Correct 980 ms 68468 KB Output is correct
40 Correct 1328 ms 68584 KB Output is correct
41 Correct 1234 ms 68904 KB Output is correct
42 Correct 1175 ms 71828 KB Output is correct
43 Correct 992 ms 92024 KB Output is correct
44 Correct 54 ms 1524 KB Output is correct
45 Correct 102 ms 1396 KB Output is correct
46 Correct 158 ms 1472 KB Output is correct
47 Correct 210 ms 1528 KB Output is correct
48 Correct 327 ms 2164 KB Output is correct
49 Correct 1372 ms 52880 KB Output is correct
50 Correct 1791 ms 69520 KB Output is correct
51 Correct 1458 ms 69644 KB Output is correct
52 Correct 2789 ms 69496 KB Output is correct
53 Correct 1324 ms 69624 KB Output is correct
54 Correct 1331 ms 69368 KB Output is correct
55 Correct 1308 ms 69512 KB Output is correct
56 Correct 133 ms 2016 KB Output is correct
57 Correct 310 ms 2148 KB Output is correct
58 Correct 539 ms 2748 KB Output is correct
59 Correct 1858 ms 69624 KB Output is correct
60 Correct 3587 ms 69544 KB Output is correct
61 Correct 1798 ms 69576 KB Output is correct
62 Correct 1389 ms 69528 KB Output is correct
63 Correct 3250 ms 69452 KB Output is correct
64 Correct 2064 ms 69472 KB Output is correct
65 Correct 2070 ms 69496 KB Output is correct
66 Correct 2053 ms 69968 KB Output is correct
67 Correct 2007 ms 72568 KB Output is correct
68 Correct 1543 ms 83804 KB Output is correct
69 Correct 3428 ms 92920 KB Output is correct