oj.uz

Submission #78704

# Submission time Handle Problem Language Result Execution time Memory
78704 2018-10-07T21:21:12 Z tincamatei Seats (IOI18_seats) C++14
70 / 100
 4000 ms 88084 KB 
#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];

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] = 0;
		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] = 0;
		fr[nod] = fr[2 * 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);
	} else {
		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;
int cells[4];
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;
	init(0, N - 1, 1);
	R = _R;
	C = _C;
	matr = new int*[1 + H + 1];
	for(int i = 0; i <= H + 1; ++i) {
		matr[i] = new int[1 + W + 1];
		for(int j = 0; j <= W + 1; ++j)
			matr[i][j] = 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)
			activateSqr(i, j, 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());
	
	for(int i = 0; i < yeet.size(); ++i) {
		if(i < yeet.size() - 1 && yeet[i] != yeet[i + 1])
			activateSqr(yeet[i].first, yeet[i].second, -1);
		else if(i == yeet.size() - 1)
			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) {
		if(i < yeet.size() - 1 && yeet[i] != yeet[i + 1])
			activateSqr(yeet[i].first, yeet[i].second, 1);
		else if(i == yeet.size() - 1)
			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:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < yeet.size(); ++i) {
                 ~~^~~~~~~~~~~~~
seats.cpp:106:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i < yeet.size() - 1 && yeet[i] != yeet[i + 1])
      ~~^~~~~~~~~~~~~~~~~
seats.cpp:108:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(i == yeet.size() - 1)
           ~~^~~~~~~~~~~~~~~~~~
seats.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < yeet.size(); ++i) {
                 ~~^~~~~~~~~~~~~
seats.cpp:115:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i < yeet.size() - 1 && yeet[i] != yeet[i + 1])
      ~~^~~~~~~~~~~~~~~~~
seats.cpp:117:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(i == yeet.size() - 1)
           ~~^~~~~~~~~~~~~~~~~~

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 508 KB Output is correct
3 Correct 37 ms 584 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 23 ms 616 KB Output is correct
6 Correct 32 ms 680 KB Output is correct
7 Correct 36 ms 680 KB Output is correct
8 Correct 31 ms 680 KB Output is correct
9 Correct 31 ms 680 KB Output is correct
10 Correct 35 ms 680 KB Output is correct
11 Correct 50 ms 680 KB Output is correct
12 Correct 23 ms 692 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 508 KB Output is correct
3 Correct 37 ms 584 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 23 ms 616 KB Output is correct
6 Correct 32 ms 680 KB Output is correct
7 Correct 36 ms 680 KB Output is correct
8 Correct 31 ms 680 KB Output is correct
9 Correct 31 ms 680 KB Output is correct
10 Correct 35 ms 680 KB Output is correct
11 Correct 50 ms 680 KB Output is correct
12 Correct 23 ms 692 KB Output is correct
13 Correct 80 ms 1420 KB Output is correct
14 Correct 96 ms 1420 KB Output is correct
15 Correct 61 ms 1452 KB Output is correct
16 Correct 40 ms 1796 KB Output is correct
17 Correct 86 ms 1796 KB Output is correct
18 Correct 90 ms 1796 KB Output is correct
19 Correct 59 ms 1796 KB Output is correct
20 Correct 52 ms 1796 KB Output is correct
21 Correct 40 ms 1796 KB Output is correct
22 Correct 42 ms 1796 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2778 ms 52796 KB Output is correct
2 Correct 1353 ms 52796 KB Output is correct
3 Correct 1243 ms 52908 KB Output is correct
4 Correct 1046 ms 52924 KB Output is correct
5 Correct 1076 ms 52924 KB Output is correct
6 Correct 1190 ms 52924 KB Output is correct
7 Correct 1113 ms 52924 KB Output is correct
8 Correct 1226 ms 52928 KB Output is correct
9 Correct 1174 ms 52928 KB Output is correct
10 Correct 1156 ms 52972 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 52972 KB Output is correct
2 Correct 186 ms 52972 KB Output is correct
3 Correct 1057 ms 52972 KB Output is correct
4 Correct 2678 ms 52972 KB Output is correct
5 Correct 952 ms 60720 KB Output is correct
6 Correct 2547 ms 88084 KB Output is correct
7 Correct 1026 ms 88084 KB Output is correct
8 Correct 1349 ms 88084 KB Output is correct
9 Correct 1278 ms 88084 KB Output is correct
10 Correct 1141 ms 88084 KB Output is correct
11 Correct 1029 ms 88084 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 88084 KB Output is correct
2 Correct 123 ms 88084 KB Output is correct
3 Correct 238 ms 88084 KB Output is correct
4 Correct 254 ms 88084 KB Output is correct
5 Correct 445 ms 88084 KB Output is correct
6 Correct 1522 ms 88084 KB Output is correct
7 Correct 1938 ms 88084 KB Output is correct
8 Correct 1482 ms 88084 KB Output is correct
9 Correct 3659 ms 88084 KB Output is correct
10 Correct 1492 ms 88084 KB Output is correct
11 Correct 1456 ms 88084 KB Output is correct
12 Correct 1372 ms 88084 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 23 ms 508 KB Output is correct
3 Correct 37 ms 584 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 23 ms 616 KB Output is correct
6 Correct 32 ms 680 KB Output is correct
7 Correct 36 ms 680 KB Output is correct
8 Correct 31 ms 680 KB Output is correct
9 Correct 31 ms 680 KB Output is correct
10 Correct 35 ms 680 KB Output is correct
11 Correct 50 ms 680 KB Output is correct
12 Correct 23 ms 692 KB Output is correct
13 Correct 80 ms 1420 KB Output is correct
14 Correct 96 ms 1420 KB Output is correct
15 Correct 61 ms 1452 KB Output is correct
16 Correct 40 ms 1796 KB Output is correct
17 Correct 86 ms 1796 KB Output is correct
18 Correct 90 ms 1796 KB Output is correct
19 Correct 59 ms 1796 KB Output is correct
20 Correct 52 ms 1796 KB Output is correct
21 Correct 40 ms 1796 KB Output is correct
22 Correct 42 ms 1796 KB Output is correct
23 Correct 2778 ms 52796 KB Output is correct
24 Correct 1353 ms 52796 KB Output is correct
25 Correct 1243 ms 52908 KB Output is correct
26 Correct 1046 ms 52924 KB Output is correct
27 Correct 1076 ms 52924 KB Output is correct
28 Correct 1190 ms 52924 KB Output is correct
29 Correct 1113 ms 52924 KB Output is correct
30 Correct 1226 ms 52928 KB Output is correct
31 Correct 1174 ms 52928 KB Output is correct
32 Correct 1156 ms 52972 KB Output is correct
33 Correct 78 ms 52972 KB Output is correct
34 Correct 186 ms 52972 KB Output is correct
35 Correct 1057 ms 52972 KB Output is correct
36 Correct 2678 ms 52972 KB Output is correct
37 Correct 952 ms 60720 KB Output is correct
38 Correct 2547 ms 88084 KB Output is correct
39 Correct 1026 ms 88084 KB Output is correct
40 Correct 1349 ms 88084 KB Output is correct
41 Correct 1278 ms 88084 KB Output is correct
42 Correct 1141 ms 88084 KB Output is correct
43 Correct 1029 ms 88084 KB Output is correct
44 Correct 59 ms 88084 KB Output is correct
45 Correct 123 ms 88084 KB Output is correct
46 Correct 238 ms 88084 KB Output is correct
47 Correct 254 ms 88084 KB Output is correct
48 Correct 445 ms 88084 KB Output is correct
49 Correct 1522 ms 88084 KB Output is correct
50 Correct 1938 ms 88084 KB Output is correct
51 Correct 1482 ms 88084 KB Output is correct
52 Correct 3659 ms 88084 KB Output is correct
53 Correct 1492 ms 88084 KB Output is correct
54 Correct 1456 ms 88084 KB Output is correct
55 Correct 1372 ms 88084 KB Output is correct
56 Correct 157 ms 88084 KB Output is correct
57 Correct 342 ms 88084 KB Output is correct
58 Correct 549 ms 88084 KB Output is correct
59 Correct 2079 ms 88084 KB Output is correct
60 Execution timed out 4040 ms 88084 KB Time limit exceeded
61 Halted 0 ms 0 KB -