oj.uz

Submission #170711

# Submission time Handle Problem Language Result Execution time Memory
170711 2019-12-26T07:11:02 Z oolimry Seats (IOI18_seats) C++14
100 / 100
 2625 ms 136904 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e9;
typedef pair<long long, int> ii;


int n, rows, cols;
static ii pos[1000005]; ///for each number, ii(r, c)
static vector<vector<int> > arr; ///arr[r*cols+c] is the element at (r,c)
///we build a grid such that the boundaries are filled with the number n

///Everything here onwards is segment tree

///This is a range min range add segment tree, but we also store the no. of occurances of the minimum element
static ii tree[2000005]; ///we store the minimum element, and the number of occurances
static long long lazy[2000005]; 


///helper function to update the value of node i from the children of i
inline void relax(int i){
	if(tree[i<<1].first == tree[i<<1|1].first){
		tree[i] = ii(tree[i<<1].first+lazy[i], tree[i<<1].second + tree[i<<1|1].second);
	} 
	else{
		tree[i] = min(tree[i<<1],tree[i<<1|1]);
		tree[i].first += lazy[i];
	}
}

void initSegment(){
	for(int i = n;i < 2 * n;i++) tree[i] = ii(0,1);
	for(int i = n - 1;i >= 0;i--) relax(i);
}

inline void update(int l, int r, long long v){
	if(l == r) return;
	int ll = l + n, rr = r - 1 + n;
	for(l += n,r += n;l < r;l>>=1,r>>=1){
		if(l&1){
			tree[l].first += v;
			lazy[l] += v;
			l++;
		}
		if(r&1){
			r--;
			tree[r].first += v;
			lazy[r] += v;
		}
	}
	while(ll > 1){
		ll >>= 1;
		relax(ll);
	}
	while(rr > 1){
		rr >>= 1;
		relax(rr);
	}
}

inline int query(){
	if(tree[1].first+lazy[1] == 4){
		return tree[1].second;
	}
	else{
		return 0;
	}
}
///segment tree ends

///consider a 2x2 square whose top-left corner is at r, c
void makeUpdate(int r, int c, bool isUndo){
	vector<int> values = {arr[r][c],arr[r+1][c],arr[r][c+1],arr[r+1][c+1]};
	sort(values.begin(),values.end());
	
	///if isReverse, we undo our previous update
	if(isUndo){
		update(values[0],values[1],-1);
		update(values[2],values[3],-inf);
	}
	else{
		update(values[0],values[1],1); ///add one to imply within that range, there is one more 2x2 square with exactly 1 black square
		update(values[2],values[3],inf); ///add infinity to "ruin" that range. When there are 2 black squares in the 2x2 square, it's impossible to have  beautiful rectangle
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H * W;
	rows = H; cols = W;
	for(int i = 0;i < rows+2;i++){
		arr.push_back({});
		arr.back().assign(cols+2,n);
	}
	for(int i = 0;i < n;i++){
		R[i]++; C[i]++;
		arr[R[i]][C[i]] = i;
		pos[i] = ii(R[i],C[i]);
	}
	
	initSegment();
	
	for(int r = 0;r <= rows;r++){
		for(int c = 0;c <= cols;c++){
			makeUpdate(r,c,false);
		}
	}	
}

int swap_seats(int a, int b) {
	ii aPos = pos[a]; ii bPos = pos[b];
	
	///undo updates for all affected rectangles
	makeUpdate(aPos.first-1,aPos.second-1,true);
	makeUpdate(aPos.first,aPos.second-1,true);
	makeUpdate(aPos.first-1,aPos.second,true);
	makeUpdate(aPos.first,aPos.second,true);
	makeUpdate(bPos.first-1,bPos.second-1,true);
	makeUpdate(bPos.first,bPos.second-1,true);
	makeUpdate(bPos.first-1,bPos.second,true);
	makeUpdate(bPos.first,bPos.second,true);
	
	
	///swapping the elements
	pos[b] = aPos; pos[a] = bPos;
	arr[aPos.first][aPos.second] = b; arr[bPos.first][bPos.second] = a;
	
	
	///now update again for all affected rectangles
	makeUpdate(aPos.first-1,aPos.second-1,false);
	makeUpdate(aPos.first,aPos.second-1,false);
	makeUpdate(aPos.first-1,aPos.second,false);
	makeUpdate(aPos.first,aPos.second,false);
	makeUpdate(bPos.first-1,bPos.second-1,false);
	makeUpdate(bPos.first,bPos.second-1,false);
	makeUpdate(bPos.first-1,bPos.second,false);
	makeUpdate(bPos.first,bPos.second,false);
	
	return query();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 504 KB Output is correct
2 Correct 25 ms 504 KB Output is correct
3 Correct 30 ms 504 KB Output is correct
4 Correct 20 ms 504 KB Output is correct
5 Correct 21 ms 504 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 31 ms 504 KB Output is correct
8 Correct 30 ms 504 KB Output is correct
9 Correct 30 ms 632 KB Output is correct
10 Correct 29 ms 504 KB Output is correct
11 Correct 27 ms 508 KB Output is correct
12 Correct 20 ms 504 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 504 KB Output is correct
2 Correct 25 ms 504 KB Output is correct
3 Correct 30 ms 504 KB Output is correct
4 Correct 20 ms 504 KB Output is correct
5 Correct 21 ms 504 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 31 ms 504 KB Output is correct
8 Correct 30 ms 504 KB Output is correct
9 Correct 30 ms 632 KB Output is correct
10 Correct 29 ms 504 KB Output is correct
11 Correct 27 ms 508 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 55 ms 1464 KB Output is correct
14 Correct 60 ms 1412 KB Output is correct
15 Correct 39 ms 1656 KB Output is correct
16 Correct 39 ms 1844 KB Output is correct
17 Correct 49 ms 1400 KB Output is correct
18 Correct 55 ms 1432 KB Output is correct
19 Correct 52 ms 1500 KB Output is correct
20 Correct 48 ms 1772 KB Output is correct
21 Correct 37 ms 1628 KB Output is correct
22 Correct 39 ms 1972 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1684 ms 89832 KB Output is correct
2 Correct 1133 ms 89296 KB Output is correct
3 Correct 1057 ms 87800 KB Output is correct
4 Correct 871 ms 89180 KB Output is correct
5 Correct 918 ms 88952 KB Output is correct
6 Correct 1014 ms 89028 KB Output is correct
7 Correct 984 ms 88696 KB Output is correct
8 Correct 906 ms 88568 KB Output is correct
9 Correct 989 ms 89008 KB Output is correct
10 Correct 992 ms 88184 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1400 KB Output is correct
2 Correct 152 ms 9212 KB Output is correct
3 Correct 881 ms 88952 KB Output is correct
4 Correct 1738 ms 88332 KB Output is correct
5 Correct 1062 ms 88728 KB Output is correct
6 Correct 1947 ms 136904 KB Output is correct
7 Correct 852 ms 87032 KB Output is correct
8 Correct 1091 ms 86376 KB Output is correct
9 Correct 1054 ms 82028 KB Output is correct
10 Correct 1054 ms 93016 KB Output is correct
11 Correct 1032 ms 109564 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2036 KB Output is correct
2 Correct 143 ms 2168 KB Output is correct
3 Correct 178 ms 2164 KB Output is correct
4 Correct 221 ms 2192 KB Output is correct
5 Correct 279 ms 3084 KB Output is correct
6 Correct 1379 ms 90632 KB Output is correct
7 Correct 1465 ms 96376 KB Output is correct
8 Correct 1389 ms 89316 KB Output is correct
9 Correct 2261 ms 95864 KB Output is correct
10 Correct 1343 ms 91756 KB Output is correct
11 Correct 1358 ms 93560 KB Output is correct
12 Correct 1357 ms 88744 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 504 KB Output is correct
2 Correct 25 ms 504 KB Output is correct
3 Correct 30 ms 504 KB Output is correct
4 Correct 20 ms 504 KB Output is correct
5 Correct 21 ms 504 KB Output is correct
6 Correct 27 ms 504 KB Output is correct
7 Correct 31 ms 504 KB Output is correct
8 Correct 30 ms 504 KB Output is correct
9 Correct 30 ms 632 KB Output is correct
10 Correct 29 ms 504 KB Output is correct
11 Correct 27 ms 508 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 55 ms 1464 KB Output is correct
14 Correct 60 ms 1412 KB Output is correct
15 Correct 39 ms 1656 KB Output is correct
16 Correct 39 ms 1844 KB Output is correct
17 Correct 49 ms 1400 KB Output is correct
18 Correct 55 ms 1432 KB Output is correct
19 Correct 52 ms 1500 KB Output is correct
20 Correct 48 ms 1772 KB Output is correct
21 Correct 37 ms 1628 KB Output is correct
22 Correct 39 ms 1972 KB Output is correct
23 Correct 1684 ms 89832 KB Output is correct
24 Correct 1133 ms 89296 KB Output is correct
25 Correct 1057 ms 87800 KB Output is correct
26 Correct 871 ms 89180 KB Output is correct
27 Correct 918 ms 88952 KB Output is correct
28 Correct 1014 ms 89028 KB Output is correct
29 Correct 984 ms 88696 KB Output is correct
30 Correct 906 ms 88568 KB Output is correct
31 Correct 989 ms 89008 KB Output is correct
32 Correct 992 ms 88184 KB Output is correct
33 Correct 56 ms 1400 KB Output is correct
34 Correct 152 ms 9212 KB Output is correct
35 Correct 881 ms 88952 KB Output is correct
36 Correct 1738 ms 88332 KB Output is correct
37 Correct 1062 ms 88728 KB Output is correct
38 Correct 1947 ms 136904 KB Output is correct
39 Correct 852 ms 87032 KB Output is correct
40 Correct 1091 ms 86376 KB Output is correct
41 Correct 1054 ms 82028 KB Output is correct
42 Correct 1054 ms 93016 KB Output is correct
43 Correct 1032 ms 109564 KB Output is correct
44 Correct 83 ms 2036 KB Output is correct
45 Correct 143 ms 2168 KB Output is correct
46 Correct 178 ms 2164 KB Output is correct
47 Correct 221 ms 2192 KB Output is correct
48 Correct 279 ms 3084 KB Output is correct
49 Correct 1379 ms 90632 KB Output is correct
50 Correct 1465 ms 96376 KB Output is correct
51 Correct 1389 ms 89316 KB Output is correct
52 Correct 2261 ms 95864 KB Output is correct
53 Correct 1343 ms 91756 KB Output is correct
54 Correct 1358 ms 93560 KB Output is correct
55 Correct 1357 ms 88744 KB Output is correct
56 Correct 165 ms 2072 KB Output is correct
57 Correct 282 ms 2036 KB Output is correct
58 Correct 502 ms 3128 KB Output is correct
59 Correct 1725 ms 86636 KB Output is correct
60 Correct 2538 ms 85624 KB Output is correct
61 Correct 1508 ms 85624 KB Output is correct
62 Correct 1561 ms 83092 KB Output is correct
63 Correct 2625 ms 88696 KB Output is correct
64 Correct 1741 ms 87032 KB Output is correct
65 Correct 1426 ms 86136 KB Output is correct
66 Correct 1823 ms 79900 KB Output is correct
67 Correct 1691 ms 90280 KB Output is correct
68 Correct 1521 ms 99596 KB Output is correct
69 Correct 2520 ms 109068 KB Output is correct