Submission #1069240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069240		0npata	Tiles (BOI24_tiles)	C++17	4 / 100	99 ms	47164 KiB

Main

#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 (stderr)

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 / 4
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10