oj.uz

답안 #784624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784624 2023-07-16T11:15:03 Z ToniB Chessboard (IZhO18_chessboard) C++17
39 / 100
 1237 ms 11840 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int MAXN = 1e5 + 5;
const int OFF = 1 << 18;
typedef long long ll;

int n, k, tour[OFF];
vector<pair<int, int> > v[MAXN];
bool prop[MAXN];

void propagate(int x, int l, int r){
	prop[x] = 0;
	tour[x] = r - l + 1 - tour[x];
	if(l != r){
		prop[x * 2 + 1] ^= 1;
		prop[x * 2 + 2] ^= 1;
	}
}

void upd(int x, int l, int r, int ql, int qr){
	if(prop[x]) propagate(x, l, r);
	if(ql <= l && r <= qr){
		prop[x] = 1;
		propagate(x, l, r);
		return ;
	}
	if(ql > r || l > qr) return ;
	int mid = (l + r) >> 1;
	upd(x * 2 + 1, l, mid, ql, qr);
	upd(x * 2 + 2, mid + 1, r, ql, qr);
	tour[x] = tour[x * 2 + 1] + tour[x * 2 + 2];
}

ll solve(int k){
	ll ret = 5e9;
	for(int b = 0; b < 2; ++b){
		memset(tour, 0, sizeof tour);
		memset(prop, 0, sizeof prop);
		ll cur = 0;
		for(int i = b * k; i < n; i += 2 * k){
			upd(0, 0, n - 1, i, i + k - 1);
		}
		for(int i = 0; i < n; ++i){
			for(pair<int, int> p : v[i]){
				upd(0, 0, n - 1, p.X, p.Y);
			}
			if(i % k == 0) upd(0, 0, n - 1, 0, n - 1);
			cur += tour[0];
		}
		ret = min(ret, cur);
	}
	return ret;
}

int main(){
	cin >> n >> k;
	for(int i = 0; i < k; ++i){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1, --y1, --x2, --y2;
		v[x1].push_back({y1, y2});
		v[x2 + 1].push_back({y1, y2});
	}
	long long ans = 5e9;
	for(int i = 1; i < n; ++i){
		if(n % i == 0){
			ans = min(ans, solve(i));
		}
	}
	cout << ans;
	return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3668 KB Output is correct
2 Correct 2 ms 3668 KB Output is correct
3 Correct 2 ms 3668 KB Output is correct
4 Correct 2 ms 3668 KB Output is correct
5 Correct 2 ms 3668 KB Output is correct
6 Correct 3 ms 3668 KB Output is correct
7 Correct 2 ms 3688 KB Output is correct
8 Correct 2 ms 3668 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 85 ms 11840 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3668 KB Output is correct
2 Correct 2 ms 3668 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Correct 5 ms 3796 KB Output is correct
5 Correct 3 ms 3696 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 3 ms 3796 KB Output is correct
9 Correct 3 ms 3692 KB Output is correct
10 Correct 2 ms 3668 KB Output is correct
11 Correct 3 ms 3796 KB Output is correct
12 Correct 2 ms 3796 KB Output is correct
13 Correct 4 ms 3808 KB Output is correct
14 Correct 4 ms 3804 KB Output is correct
15 Correct 5 ms 3800 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3668 KB Output is correct
2 Correct 2 ms 3668 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Correct 5 ms 3796 KB Output is correct
5 Correct 3 ms 3696 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 3 ms 3796 KB Output is correct
9 Correct 3 ms 3692 KB Output is correct
10 Correct 2 ms 3668 KB Output is correct
11 Correct 3 ms 3796 KB Output is correct
12 Correct 2 ms 3796 KB Output is correct
13 Correct 4 ms 3808 KB Output is correct
14 Correct 4 ms 3804 KB Output is correct
15 Correct 5 ms 3800 KB Output is correct
16 Correct 60 ms 4896 KB Output is correct
17 Correct 99 ms 7300 KB Output is correct
18 Correct 205 ms 7620 KB Output is correct
19 Correct 1143 ms 7248 KB Output is correct
20 Correct 1237 ms 7628 KB Output is correct
21 Correct 103 ms 7328 KB Output is correct
22 Correct 7 ms 3688 KB Output is correct
23 Correct 166 ms 5560 KB Output is correct
24 Correct 186 ms 7456 KB Output is correct
25 Correct 38 ms 4076 KB Output is correct
26 Correct 117 ms 6024 KB Output is correct
27 Correct 210 ms 6808 KB Output is correct
28 Correct 198 ms 7472 KB Output is correct
29 Correct 41 ms 5204 KB Output is correct
30 Correct 8 ms 3796 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 85 ms 11840 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3668 KB Output is correct
2 Correct 2 ms 3668 KB Output is correct
3 Correct 2 ms 3668 KB Output is correct
4 Correct 2 ms 3668 KB Output is correct
5 Correct 2 ms 3668 KB Output is correct
6 Correct 3 ms 3668 KB Output is correct
7 Correct 2 ms 3688 KB Output is correct
8 Correct 2 ms 3668 KB Output is correct
9 Runtime error 85 ms 11840 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -