oj.uz

Submission #130118

# Submission time Handle Problem Language Result Execution time Memory
130118 2019-07-14T03:58:52 Z WannnabeIOI Seats (IOI18_seats) C++14
100 / 100
 3419 ms 214112 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 5 + 1000000;
const int MAXT = 2100000;

int n, m;
vector<vector<int>> G;
vector<vector<char>> is_valid;
vector<int> R, C;
pi val[MAXN];

void ADD(pi &a, pi b){
	a.first += b.first;
	a.second += b.second;
}

struct seg{
	pi tree[MAXT];
	pi lazy[MAXT];
	int cnt_min[MAXT];
	void lazydown(int p){
		ADD(tree[2*p], lazy[p]);
		ADD(tree[2*p+1], lazy[p]);
		ADD(lazy[2*p], lazy[p]);
		ADD(lazy[2*p+1], lazy[p]);
		lazy[p] = pi(0, 0);
	}
	void eat(int p){
		tree[p] = min(tree[2*p], tree[2*p+1]);
		cnt_min[p] = 0;
		if(tree[p] == tree[2*p]) cnt_min[p] += cnt_min[2*p];
		if(tree[p] == tree[2*p+1]) cnt_min[p] += cnt_min[2*p+1];
	}
	void init(int s, int e, int p){
		if(s == e){
			cnt_min[p] = 1;
			return;
		}
		int m = (s+e)/2;
		init(s, m, 2*p);
		init(m+1, e, 2*p+1);
		eat(p);
	}
	void add(int s, int e, int ps, int pe, int p, pi v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			ADD(tree[p], v);
			ADD(lazy[p], v);
			return;
		}
		int pm = (ps+pe)/2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		eat(p);
	}
	int query(){
		return tree[1] == pi(4, 0) ? cnt_min[1] : 0;
	}
}seg;

pi mp[MAXN];
vector<int> updp; 

void flush(){
	sort(updp.begin(), updp.end());
	updp.resize(unique(updp.begin(), updp.end()) - updp.begin());
	auto v = pi(0, 0);
	for(int i=0; i+1<updp.size(); i++){
		ADD(v, mp[updp[i]]);
		seg.add(updp[i], updp[i + 1] - 1, 0, n * m - 1, 1, v);
	}
	for(auto &i : updp) mp[i] = pi(0, 0);
	updp.clear();
}

void update(int x, int y, int f){
	if(is_valid[x][y] == 0 && f == -1) return;
	if(is_valid[x][y] == 1 && f == 1) return;
	is_valid[x][y] ^= 1;
	vector<pi> times;
	times.emplace_back(G[x][y], 0);
	times.emplace_back(G[x + 1][y], 1);
	times.emplace_back(G[x + 1][y + 1], 2);
	times.emplace_back(G[x][y + 1], 3);
	sort(times.begin(), times.end());
	for(int i=0; i<3; i++){
		int starting_time = times[i].first;
		int ending_time = times[i + 1].first;
		starting_time = max(starting_time, 0);
		ending_time = min(ending_time, n * m);
		if(starting_time >= ending_time) continue;
		pi updates;
		if(i == 0){
			updates = pi(f, 0);
		}
		if(i == 1){
			if((times[0].second ^ times[1].second) == 2){
				updates = pi(2 * f, 0);
			}
			else continue;
		}
		if(i == 2){
			updates = pi(0, f);
		}
		ADD(mp[starting_time], updates);
		ADD(mp[ending_time], pi(-updates.first, -updates.second));
		updp.push_back(starting_time);
		updp.push_back(ending_time);
	}
}

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
	G.resize(H + 2);
	for(auto &i : G) i.resize(W + 2);
	for(auto &i : G) for(auto &j : i) j = 1e7;
	is_valid.resize(H + 1);
	for(auto &i : is_valid) i.resize(W + 1);
	n = H, m = W, R = _R, C = _C;
	for(int i=0; i<n*m; i++){
		G[R[i] + 1][C[i] + 1] = i;
	}
	for(int i=0; i<n+1; i++){
		for(int j=0; j<m+1; j++){
			update(i, j, 1);
		}
	}
	seg.init(0, n*m-1, 1);
}

int swap_seats(int a, int b) {
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			update(R[a] + i, C[a] + j, -1);
			update(R[b] + i, C[b] + j, -1);
		}
	}
	swap(G[R[a] + 1][C[a] + 1], G[R[b] + 1][C[b] + 1]);
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			update(R[a] + i, C[a] + j, 1);
			update(R[b] + i, C[b] + j, 1);
		}
	}
	flush();
	return seg.query();
}

Compilation message

seats.cpp: In function 'void flush()':
seats.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<updp.size(); i++){
               ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33400 KB Output is correct
2 Correct 64 ms 33400 KB Output is correct
3 Correct 75 ms 33528 KB Output is correct
4 Correct 57 ms 33400 KB Output is correct
5 Correct 53 ms 33400 KB Output is correct
6 Correct 68 ms 33400 KB Output is correct
7 Correct 71 ms 33400 KB Output is correct
8 Correct 70 ms 33528 KB Output is correct
9 Correct 70 ms 33400 KB Output is correct
10 Correct 71 ms 33400 KB Output is correct
11 Correct 71 ms 33400 KB Output is correct
12 Correct 54 ms 33400 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33400 KB Output is correct
2 Correct 64 ms 33400 KB Output is correct
3 Correct 75 ms 33528 KB Output is correct
4 Correct 57 ms 33400 KB Output is correct
5 Correct 53 ms 33400 KB Output is correct
6 Correct 68 ms 33400 KB Output is correct
7 Correct 71 ms 33400 KB Output is correct
8 Correct 70 ms 33528 KB Output is correct
9 Correct 70 ms 33400 KB Output is correct
10 Correct 71 ms 33400 KB Output is correct
11 Correct 71 ms 33400 KB Output is correct
12 Correct 54 ms 33400 KB Output is correct
13 Correct 113 ms 34304 KB Output is correct
14 Correct 121 ms 34268 KB Output is correct
15 Correct 86 ms 34424 KB Output is correct
16 Correct 89 ms 35316 KB Output is correct
17 Correct 95 ms 34292 KB Output is correct
18 Correct 102 ms 34280 KB Output is correct
19 Correct 98 ms 34296 KB Output is correct
20 Correct 86 ms 34932 KB Output is correct
21 Correct 71 ms 34296 KB Output is correct
22 Correct 75 ms 35448 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1859 ms 118596 KB Output is correct
2 Correct 1427 ms 109632 KB Output is correct
3 Correct 1453 ms 109620 KB Output is correct
4 Correct 1354 ms 109504 KB Output is correct
5 Correct 1349 ms 109716 KB Output is correct
6 Correct 1306 ms 109604 KB Output is correct
7 Correct 1399 ms 109568 KB Output is correct
8 Correct 1456 ms 109640 KB Output is correct
9 Correct 1412 ms 109668 KB Output is correct
10 Correct 1380 ms 109548 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 34328 KB Output is correct
2 Correct 236 ms 40476 KB Output is correct
3 Correct 1683 ms 109676 KB Output is correct
4 Correct 1868 ms 118608 KB Output is correct
5 Correct 1674 ms 118388 KB Output is correct
6 Correct 2208 ms 214112 KB Output is correct
7 Correct 1417 ms 112452 KB Output is correct
8 Correct 1385 ms 109640 KB Output is correct
9 Correct 1488 ms 110088 KB Output is correct
10 Correct 1461 ms 118788 KB Output is correct
11 Correct 1546 ms 159372 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 34976 KB Output is correct
2 Correct 248 ms 34932 KB Output is correct
3 Correct 274 ms 35084 KB Output is correct
4 Correct 310 ms 35060 KB Output is correct
5 Correct 421 ms 35872 KB Output is correct
6 Correct 2160 ms 119356 KB Output is correct
7 Correct 2047 ms 119248 KB Output is correct
8 Correct 2140 ms 119336 KB Output is correct
9 Correct 2544 ms 119360 KB Output is correct
10 Correct 2085 ms 119360 KB Output is correct
11 Correct 2139 ms 119312 KB Output is correct
12 Correct 2036 ms 119260 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33400 KB Output is correct
2 Correct 64 ms 33400 KB Output is correct
3 Correct 75 ms 33528 KB Output is correct
4 Correct 57 ms 33400 KB Output is correct
5 Correct 53 ms 33400 KB Output is correct
6 Correct 68 ms 33400 KB Output is correct
7 Correct 71 ms 33400 KB Output is correct
8 Correct 70 ms 33528 KB Output is correct
9 Correct 70 ms 33400 KB Output is correct
10 Correct 71 ms 33400 KB Output is correct
11 Correct 71 ms 33400 KB Output is correct
12 Correct 54 ms 33400 KB Output is correct
13 Correct 113 ms 34304 KB Output is correct
14 Correct 121 ms 34268 KB Output is correct
15 Correct 86 ms 34424 KB Output is correct
16 Correct 89 ms 35316 KB Output is correct
17 Correct 95 ms 34292 KB Output is correct
18 Correct 102 ms 34280 KB Output is correct
19 Correct 98 ms 34296 KB Output is correct
20 Correct 86 ms 34932 KB Output is correct
21 Correct 71 ms 34296 KB Output is correct
22 Correct 75 ms 35448 KB Output is correct
23 Correct 1859 ms 118596 KB Output is correct
24 Correct 1427 ms 109632 KB Output is correct
25 Correct 1453 ms 109620 KB Output is correct
26 Correct 1354 ms 109504 KB Output is correct
27 Correct 1349 ms 109716 KB Output is correct
28 Correct 1306 ms 109604 KB Output is correct
29 Correct 1399 ms 109568 KB Output is correct
30 Correct 1456 ms 109640 KB Output is correct
31 Correct 1412 ms 109668 KB Output is correct
32 Correct 1380 ms 109548 KB Output is correct
33 Correct 115 ms 34328 KB Output is correct
34 Correct 236 ms 40476 KB Output is correct
35 Correct 1683 ms 109676 KB Output is correct
36 Correct 1868 ms 118608 KB Output is correct
37 Correct 1674 ms 118388 KB Output is correct
38 Correct 2208 ms 214112 KB Output is correct
39 Correct 1417 ms 112452 KB Output is correct
40 Correct 1385 ms 109640 KB Output is correct
41 Correct 1488 ms 110088 KB Output is correct
42 Correct 1461 ms 118788 KB Output is correct
43 Correct 1546 ms 159372 KB Output is correct
44 Correct 205 ms 34976 KB Output is correct
45 Correct 248 ms 34932 KB Output is correct
46 Correct 274 ms 35084 KB Output is correct
47 Correct 310 ms 35060 KB Output is correct
48 Correct 421 ms 35872 KB Output is correct
49 Correct 2160 ms 119356 KB Output is correct
50 Correct 2047 ms 119248 KB Output is correct
51 Correct 2140 ms 119336 KB Output is correct
52 Correct 2544 ms 119360 KB Output is correct
53 Correct 2085 ms 119360 KB Output is correct
54 Correct 2139 ms 119312 KB Output is correct
55 Correct 2036 ms 119260 KB Output is correct
56 Correct 283 ms 34916 KB Output is correct
57 Correct 487 ms 35060 KB Output is correct
58 Correct 691 ms 35892 KB Output is correct
59 Correct 2444 ms 110428 KB Output is correct
60 Correct 3419 ms 119508 KB Output is correct
61 Correct 2253 ms 110528 KB Output is correct
62 Correct 2141 ms 114876 KB Output is correct
63 Correct 3227 ms 122432 KB Output is correct
64 Correct 2425 ms 111940 KB Output is correct
65 Correct 2150 ms 110396 KB Output is correct
66 Correct 2635 ms 111168 KB Output is correct
67 Correct 2633 ms 120304 KB Output is correct
68 Correct 2144 ms 142028 KB Output is correct
69 Correct 3286 ms 169304 KB Output is correct