oj.uz

Submission #78707

# Submission time Handle Problem Language Result Execution time Memory
78707 2018-10-07T21:52:02 Z tincamatei Seats (IOI18_seats) C++14
100 / 100
 2145 ms 151180 KB 
#pragma GCC target("avx,avx2,sse,sse2")
#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;

int val[1+4*MAX_N], fr[1+4*MAX_N];
int lazy[1+4*MAX_N];
int initsum[MAX_N+1];

static inline void pushLazy(int nod, int l, int r) {
	if(lazy[nod] != 0) {
		val[nod] += lazy[nod];
		if(l < r) {
			lazy[2 * nod] += lazy[nod];
			lazy[2 * nod + 1] += lazy[nod];
		}
		lazy[nod] = 0;
	}
}

inline void init(int l, int r, int nod = 1) {
	if(l == r) {
		val[nod] = initsum[l];
		fr[nod] = 1;
	}
	else if(l < r){
		int mid = (l + r) / 2;
		init(l, mid, 2 * nod);
		init(mid + 1, r, 2 * nod + 1);
		val[nod] = min(val[2 * nod], val[2 * nod + 1]);
		if(val[2 * nod] == val[nod])
			fr[nod] += fr[2 * nod];
		if(val[2 * nod + 1] == val[nod])
			fr[nod] += fr[2 * nod + 1];
	}
}

inline void update(int i, int j, int valU, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(r < i || j < l)
		return;
	
	int mid = (l + r) / 2;
	if(i <= l && r <= j) {
		lazy[nod] += valU;
		pushLazy(nod, l, r);
		return;
	}
	update(i, j, valU, l, mid, 2 * nod);
	update(i, j, valU, mid + 1, r, 2 * nod + 1);
	val[nod] = val[2 * nod], fr[nod] = fr[2 * nod];
	if(val[2 * nod + 1] < val[nod]) {
		val[nod] = val[2 * nod + 1];
		fr[nod] = fr[2 * nod + 1];
	} else if(val[nod] == val[2 * nod + 1])
		fr[nod] += fr[2 * nod + 1];
}

int N, H, W;
int cells[4];
vector<vector<int> > matr;

vector<int> R, C;

static inline void activateSqr(int l, int c, int x) {
	cells[0] = matr[l][c];
	cells[1] = matr[l + 1][c];
	cells[2] = matr[l][c + 1];
	cells[3] = matr[l + 1][c + 1];
	std::sort(cells, cells + 4);
	update(cells[0], cells[1] - 1, x, 0, N - 1);
	update(cells[2], cells[3] - 1, 4 * x, 0, N - 1);
}

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
	N = H * W;
	R = _R;
	C = _C;
	matr.resize(H+2, vector<int>(W+2, N));

	for(int i = 0; i < N; ++i) {
		R[i]++;
		C[i]++;
		matr[R[i]][C[i]] = i;
	}
	for(int i = 0; i <= H; ++i)
		for(int j = 0; j <= W; ++j) {
			cells[0] = matr[i][j];
			cells[1] = matr[i + 1][j];
			cells[2] = matr[i][j + 1];
			cells[3] = matr[i + 1][j + 1];
			std::sort(cells, cells + 4);
			initsum[cells[0]]++;
			initsum[cells[1]]--;
			initsum[cells[2]]+=4;
			initsum[cells[3]]-=4;
		}
	
	for(int i = 1; i < N; ++i)
		initsum[i] += initsum[i - 1];
	init(0, N - 1, 1);
}

int dr[] = {0,-1, 0, -1};
int dc[] = {0, 0,-1, -1};

int swap_seats(int a, int b) {
	vector<pair<int, int> > yeet;
	for(int i = 0; i < 4; ++i) {
		yeet.push_back(make_pair(R[a] + dr[i], C[a] + dc[i]));
		yeet.push_back(make_pair(R[b] + dr[i], C[b] + dc[i]));
	}
	std::sort(yeet.begin(), yeet.end());
	yeet.resize(unique(yeet.begin(), yeet.end()) - yeet.begin());	
	for(int i = 0; i < yeet.size(); ++i)
		activateSqr(yeet[i].first, yeet[i].second, -1);
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	swap(matr[R[a]][C[a]], matr[R[b]][C[b]]);
	for(int i = 0; i < yeet.size(); ++i)
		activateSqr(yeet[i].first, yeet[i].second, 1);
	
	if(val[1] != 4)
		return 0;
	return fr[1];
}

Compilation message

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < yeet.size(); ++i)
                 ~~^~~~~~~~~~~~~
seats.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < yeet.size(); ++i)
                 ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 36 ms 552 KB Output is correct
4 Correct 25 ms 644 KB Output is correct
5 Correct 20 ms 736 KB Output is correct
6 Correct 34 ms 840 KB Output is correct
7 Correct 34 ms 840 KB Output is correct
8 Correct 32 ms 840 KB Output is correct
9 Correct 30 ms 840 KB Output is correct
10 Correct 34 ms 840 KB Output is correct
11 Correct 41 ms 840 KB Output is correct
12 Correct 24 ms 840 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 36 ms 552 KB Output is correct
4 Correct 25 ms 644 KB Output is correct
5 Correct 20 ms 736 KB Output is correct
6 Correct 34 ms 840 KB Output is correct
7 Correct 34 ms 840 KB Output is correct
8 Correct 32 ms 840 KB Output is correct
9 Correct 30 ms 840 KB Output is correct
10 Correct 34 ms 840 KB Output is correct
11 Correct 41 ms 840 KB Output is correct
12 Correct 24 ms 840 KB Output is correct
13 Correct 85 ms 1388 KB Output is correct
14 Correct 90 ms 1388 KB Output is correct
15 Correct 51 ms 1528 KB Output is correct
16 Correct 40 ms 1912 KB Output is correct
17 Correct 61 ms 1912 KB Output is correct
18 Correct 72 ms 1912 KB Output is correct
19 Correct 54 ms 1912 KB Output is correct
20 Correct 47 ms 1912 KB Output is correct
21 Correct 36 ms 1912 KB Output is correct
22 Correct 38 ms 1972 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 48980 KB Output is correct
2 Correct 493 ms 48980 KB Output is correct
3 Correct 498 ms 49072 KB Output is correct
4 Correct 449 ms 49072 KB Output is correct
5 Correct 450 ms 49072 KB Output is correct
6 Correct 467 ms 49072 KB Output is correct
7 Correct 507 ms 49072 KB Output is correct
8 Correct 532 ms 49072 KB Output is correct
9 Correct 457 ms 49196 KB Output is correct
10 Correct 461 ms 49196 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 49196 KB Output is correct
2 Correct 120 ms 49196 KB Output is correct
3 Correct 475 ms 49196 KB Output is correct
4 Correct 719 ms 49196 KB Output is correct
5 Correct 492 ms 56800 KB Output is correct
6 Correct 880 ms 100008 KB Output is correct
7 Correct 461 ms 100008 KB Output is correct
8 Correct 489 ms 100008 KB Output is correct
9 Correct 519 ms 100008 KB Output is correct
10 Correct 463 ms 100008 KB Output is correct
11 Correct 470 ms 100008 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 100008 KB Output is correct
2 Correct 125 ms 100008 KB Output is correct
3 Correct 223 ms 100008 KB Output is correct
4 Correct 250 ms 100008 KB Output is correct
5 Correct 422 ms 100008 KB Output is correct
6 Correct 990 ms 100008 KB Output is correct
7 Correct 1031 ms 100008 KB Output is correct
8 Correct 965 ms 100008 KB Output is correct
9 Correct 1299 ms 100008 KB Output is correct
10 Correct 858 ms 100008 KB Output is correct
11 Correct 875 ms 100008 KB Output is correct
12 Correct 899 ms 100008 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 36 ms 552 KB Output is correct
4 Correct 25 ms 644 KB Output is correct
5 Correct 20 ms 736 KB Output is correct
6 Correct 34 ms 840 KB Output is correct
7 Correct 34 ms 840 KB Output is correct
8 Correct 32 ms 840 KB Output is correct
9 Correct 30 ms 840 KB Output is correct
10 Correct 34 ms 840 KB Output is correct
11 Correct 41 ms 840 KB Output is correct
12 Correct 24 ms 840 KB Output is correct
13 Correct 85 ms 1388 KB Output is correct
14 Correct 90 ms 1388 KB Output is correct
15 Correct 51 ms 1528 KB Output is correct
16 Correct 40 ms 1912 KB Output is correct
17 Correct 61 ms 1912 KB Output is correct
18 Correct 72 ms 1912 KB Output is correct
19 Correct 54 ms 1912 KB Output is correct
20 Correct 47 ms 1912 KB Output is correct
21 Correct 36 ms 1912 KB Output is correct
22 Correct 38 ms 1972 KB Output is correct
23 Correct 580 ms 48980 KB Output is correct
24 Correct 493 ms 48980 KB Output is correct
25 Correct 498 ms 49072 KB Output is correct
26 Correct 449 ms 49072 KB Output is correct
27 Correct 450 ms 49072 KB Output is correct
28 Correct 467 ms 49072 KB Output is correct
29 Correct 507 ms 49072 KB Output is correct
30 Correct 532 ms 49072 KB Output is correct
31 Correct 457 ms 49196 KB Output is correct
32 Correct 461 ms 49196 KB Output is correct
33 Correct 74 ms 49196 KB Output is correct
34 Correct 120 ms 49196 KB Output is correct
35 Correct 475 ms 49196 KB Output is correct
36 Correct 719 ms 49196 KB Output is correct
37 Correct 492 ms 56800 KB Output is correct
38 Correct 880 ms 100008 KB Output is correct
39 Correct 461 ms 100008 KB Output is correct
40 Correct 489 ms 100008 KB Output is correct
41 Correct 519 ms 100008 KB Output is correct
42 Correct 463 ms 100008 KB Output is correct
43 Correct 470 ms 100008 KB Output is correct
44 Correct 66 ms 100008 KB Output is correct
45 Correct 125 ms 100008 KB Output is correct
46 Correct 223 ms 100008 KB Output is correct
47 Correct 250 ms 100008 KB Output is correct
48 Correct 422 ms 100008 KB Output is correct
49 Correct 990 ms 100008 KB Output is correct
50 Correct 1031 ms 100008 KB Output is correct
51 Correct 965 ms 100008 KB Output is correct
52 Correct 1299 ms 100008 KB Output is correct
53 Correct 858 ms 100008 KB Output is correct
54 Correct 875 ms 100008 KB Output is correct
55 Correct 899 ms 100008 KB Output is correct
56 Correct 139 ms 100008 KB Output is correct
57 Correct 355 ms 100008 KB Output is correct
58 Correct 586 ms 100008 KB Output is correct
59 Correct 1516 ms 100008 KB Output is correct
60 Correct 2145 ms 100008 KB Output is correct
61 Correct 1260 ms 100008 KB Output is correct
62 Correct 1057 ms 100008 KB Output is correct
63 Correct 1830 ms 100008 KB Output is correct
64 Correct 1389 ms 100008 KB Output is correct
65 Correct 1198 ms 100008 KB Output is correct
66 Correct 1668 ms 100008 KB Output is correct
67 Correct 1574 ms 100008 KB Output is correct
68 Correct 1109 ms 125512 KB Output is correct
69 Correct 1884 ms 151180 KB Output is correct