oj.uz

Submission #1069240

# Submission time Handle Problem Language Result Execution time Memory
1069240 2024-08-21T17:59:58 Z 0npata Tiles (BOI24_tiles) C++17
4 / 100
 99 ms 47164 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector
#define arr array

const int INF = 1e17;

struct SegNode {
	int size = 0;
	int cnt_one = 0;
	arr<int, 2> pref_cnt{0, 0};
	arr<int, 2> suf_cnt{0, 0};
	bool valid = true;

	bool valid_all() {
		return valid && ((pref_cnt[0] % 2) + (pref_cnt[1] % 2) + (suf_cnt[0] % 2) + (suf_cnt[1] % 2) == 0);
	}

	void debug() {
		//cerr << size << ' ' << cnt_one  << ' ' << pref_cnt[0] << ' ' << pref_cnt[1] <<' ' << valid << '\n';
	}


	SegNode merge(SegNode other) {
		arr<int, 2> pref_cnt_n;
		arr<int, 2> suf_cnt_n;
		bool valid_n = valid & other.valid;

		assert(pref_cnt[0] == 0 || pref_cnt[1] == 0);
		assert(suf_cnt[0] == 0 || suf_cnt[1] == 0);

		if(size+other.size == cnt_one+other.cnt_one || 0 == cnt_one+other.cnt_one) {
			pref_cnt_n = {pref_cnt[0]+other.pref_cnt[0], pref_cnt[1]+other.pref_cnt[1]};
			suf_cnt_n = pref_cnt_n;
		}
		else {
			pref_cnt_n = pref_cnt;
			suf_cnt_n = other.suf_cnt;
			arr<int, 2> mid_cnt = {suf_cnt[0]+other.pref_cnt[0], suf_cnt[1]+other.pref_cnt[1]};
			valid &= (mid_cnt[0] % 2 == 0) & (mid_cnt[1] % 2 == 0);
		}

		return {size + other.size, cnt_one+other.cnt_one, pref_cnt_n, suf_cnt_n, valid_n};
	}


	SegNode invert() {
		return {size, size-cnt_one, {pref_cnt[1], pref_cnt[0]}, {suf_cnt[1], suf_cnt[0]}, valid};
	}
};

struct SegTree {
	int n;
	vec<SegNode> data;
	vec<bool> lazy;

	SegTree(int n_i) {
		n = 1;
		while(n < n_i) n*= 2;
		data = vec<SegNode>(n*2);
		for(int i = n; i<n*2; i++) {
			data[i].size = 1;
			data[i].pref_cnt = {1, 0};
			data[i].suf_cnt = {1, 0};
		}
		for(int i = n-1; i>=1; i--) {
			data[i] = data[i*2].merge(data[i*2+1]);
		}
		lazy = vec<bool>(n*2);
	}

	void push(int i) {
		if(!lazy[i]) {
			return;
		}
		lazy[i] = false;
		data[i] = data[i].invert();
		if(i*2 > n*2) {
			return;
		}
		lazy[i*2] = !lazy[i*2];
		lazy[i*2+1] = !lazy[i*2+1];
	}

	SegNode _query(int l, int r, int ti, int tl, int tr) {
		push(ti);
		if(tl >= r || tr <= l) {
			return {};
		}
		if(tl >= l && tr <= r) {
			return data[ti];
		}
		int tm = (tl+tr)/2;
		return _query(l, r, ti*2, tl, tm).merge(_query(l, r, ti*2+1, tm, tr));
	}

	SegNode query(int l, int r) {
		return _query(l, r, 1, 0, n);
	}

	void _invert(int l, int r, int ti, int tl, int tr) {
		push(ti);
		if(tl >= r || tr <= l) {
			return;
		}
		if(l <= tl && r >= tr) {
			lazy[ti] = true;
			push(ti);
			return;
		}

		int tm = (tl+tr)/2;
		_invert(l, r, ti*2, tl, tm);
		_invert(l, r, ti*2+1, tm, tr);
		data[ti] = data[ti*2].merge(data[ti*2+1]);
	}

	void invert(int l, int r) {
		_invert(l, r, 1, 0, n);
	}

};

struct Triple {
	int first;
	int second;
	int third;
};

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, M;
	cin >> N >> M;


	vec<pair<int, int>> ps(N);
	vec<int> ys(N);
	for(int i = 0; i<N; i++) {
		cin >> ps[i].first >> ps[i].second;
		ys[i] = ps[i].second;
	}

	SegTree st(1005);

	sort(ys.begin(), ys.end());
	map<int, int> ycompr;
	int sub = ys[0];

	for(int i = 0; i<ys.size(); i++) {
		if(i>0) {
			int diff = ys[i]-ys[i-1];
			if(diff > 0) {
				sub += diff;
				sub -= 2;
				sub += diff%2;
			}
		}
		ycompr[ys[i]] = ys[i]-sub;
	}

	for(int i = 0; i<N; i++) ps[i].second = ycompr[ps[i].second];

	map<int, vec<pair<int, int>>> versegs;

	for(int i = 0; i<N; i++) {
		if(ps[i].first == ps[(i+1)%N].first) {
			versegs[ps[i].first].push_back({min(ps[i].second, ps[(i+1)%N].second), max(ps[i].second, ps[(i+1)%N].second)});
		}
	}


 	int ans = M;

	map<int, Triple> actsegs;

	auto handlerectangle = [&](int l, int r, int u, int d, int bst) {
		if(r-l == 0) return;
		auto node = st.query(d, u);
		node.debug();
		if(!node.valid_all()) {
			ans = min(ans, bst);
			//cerr << "VL: " << bst << '\n';
		}
		else {
			assert((u-d) % 2 == 0);
		}

		if((r-l) % 2) st.invert(d, u);
	};

	auto insert = [&](pair<int, Triple> actseg) {
		int third = st.query(actseg.first, actseg.second.first).cnt_one == 0 ? actseg.second.second : actseg.second.third;
		actsegs.insert({actseg.first, {actseg.second.first, actseg.second.second, third}});
	};

	for(auto [x, versegs_x] : versegs) {
		for(auto verseg : versegs_x) {
			auto actseg_u_it = actsegs.upper_bound(verseg.first);
			if(actseg_u_it != actsegs.begin()) {
				auto actseg_d_it = actseg_u_it;
				actseg_d_it--;
				auto actseg_d = *actseg_d_it;
				if(actseg_d.first <= verseg.first && actseg_d.second.first > verseg.first) {
					assert(actseg_d.second.first >= verseg.second);
					handlerectangle(actseg_d.second.second, x, actseg_d.second.first, actseg_d.first, actseg_d.second.third);
					// removal
					actsegs.erase(actseg_d.first);
					if(verseg.first > actseg_d.first) {
						insert({actseg_d.first, {verseg.first, x, actseg_d.second.third}});
					}
					if(verseg.second < actseg_d.second.first) {
						insert({verseg.second, {actseg_d.second.first, x, actseg_d.second.third}});
					}
					if(st.query(verseg.first, verseg.second).cnt_one != 0) {
						ans = min(ans, actseg_d.second.third==actseg_d.second.second ? x-1 : actseg_d.second.third);
					}
					continue;
				}
			}

			int bst = x;

			// we haven't removed anything, maybe we are touchign tho
			actseg_u_it = actsegs.upper_bound(verseg.first);
			if(actseg_u_it != actsegs.end()) {
				auto actseg_u = *actseg_u_it;
				assert(actseg_u.first >= verseg.second);
				if(actseg_u.first == verseg.second) {
					actsegs.erase(actseg_u.first);
					handlerectangle(actseg_u.second.second, x, actseg_u.second.first, actseg_u.first, actseg_u.second.third);
					verseg.second = actseg_u.second.first;

					if(st.query(actseg_u.first, actseg_u.second.first).cnt_one != 0) {
						//cerr << actseg_u.second.third << ' ' << actseg_u.second.second << '\n';
						bst = min(bst, actseg_u.second.third==actseg_u.second.second ? x-1 : actseg_u.second.third);
					}
				}
			}
			actseg_u_it = actsegs.upper_bound(verseg.first);
			if(actseg_u_it != actsegs.begin()) {
				auto actseg_d_it = actseg_u_it;
				actseg_d_it--;
				auto actseg_d = *actseg_d_it;
				assert(actseg_d.second.first <= verseg.first);
				if(actseg_d.second.first == verseg.first) {
					actsegs.erase(actseg_d.first);
					handlerectangle(actseg_d.second.second, x, actseg_d.second.first, actseg_d.first, actseg_d.second.third);
					verseg.first = actseg_d.first;

					if(st.query(actseg_d.first, actseg_d.second.first).cnt_one != 0) {
						bst = min(bst, actseg_d.second.third==actseg_d.second.second ? x-1 : actseg_d.second.third);
					}
				}
			}

			insert({verseg.first, {verseg.second, x, bst}});
		}
	}

	cout << ans << '\n';
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:153:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |  for(int i = 0; i<ys.size(); i++) {
      |                 ~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Runtime error 1 ms 860 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 57 ms 13424 KB Output is correct
3 Incorrect 50 ms 13416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 47164 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Runtime error 1 ms 860 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -