Submission #1088924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088924		raczek	Tiles (BOI24_tiles)	C++17	49 / 100	57 ms	9324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	set<pair<int, int> > segs[2]; //.first = koniec, .second = poczatek
	vector<int> np(2);
	int result = 0;
	auto add = [&](int x, int y1, int y2)
	{
		x = x%2;
		auto it = segs[x].insert({y2, y1}).first;
		if(abs(y2 - y1)%2 == 1) np[x]++;
		if(it != segs[x].begin())
		{
			it--;
			if(it->first == y1)
			{
				if(abs(it->first - it->second)%2 == 1) np[x]--;
				if(abs(y2 - y1)%2 == 1) np[x]--;
				segs[x].erase(make_pair(it->first, it->second));
				segs[x].erase(make_pair(y2, y1));
				y1 = it->second;
				it = segs[x].insert(make_pair(y2, y1)).first;
				if(abs(y2 - y1)%2 == 1) np[x]++;
			}
			else
			it++;
		}
		it++;
		if(it != segs[x].end())
		{
			if(it->second == y2)
			{
				if(abs(it->first - it->second)%2 == 1) np[x]--;
				if(abs(y1 - y2)%2 == 1) np[x]--;
				segs[x].erase(make_pair(it->first, it->second));
				segs[x].erase(make_pair(y2, y1));
				y2 = it->first;
				segs[x].insert(make_pair(y2, y1));
				if(abs(y2 - y1)%2 == 1) np[x]++;
			}
		}
	};
	auto sub = [&](int x, int y1, int y2)
	{
		x = x%2; x^=1;
		auto it1 = segs[x].upper_bound(make_pair(y1, -1));
		if(it1 != segs[x].end() && it1->second <= y1) {cout<<result; exit(0);}
		auto it2 = segs[x].upper_bound(make_pair(y2, -1));
		if(it2 != segs[x].end() && it2->second <= y2) {cout<<result; exit(0);}
		if(it1 != it2) {cout<<result; exit(0);}
		x^=1;
		vector<pair<int, int> > toAdd;
		vector<pair<int, int> > toSub;
		for(auto it = segs[x].upper_bound(make_pair(y1, -1)); it != segs[x].end() 
		&& it->second <= y2; ++it)
		{
			toSub.push_back(*it);
			if(abs(it->first - it->second)%2 == 1) np[x]--;
			if(it->second < y1)
			{
				if(abs(it->second - y1)%2 == 1) np[x]++;
				toAdd.push_back(make_pair(y1, it->second));
			}
			if(it->first > y2)
			{
				if(abs(it->first - y2)%2 == 1) np[x]++;
				toAdd.push_back(make_pair(it->first, y2));
			}
		}
		for(auto v : toSub) segs[x].erase(v);
		for(auto v : toAdd) segs[x].insert(v);
	};
	int n, m;
	cin>>n>>m;
	vector<pair<int, int> > pts(n);
	for(auto& v : pts) {cin>>v.first>>v.second;}
	auto cmp = [&](pair<int, int> a, pair<int, int> b) {
		long long ax = a.first, ay = a.second, bx = b.first, by = b.second;
		return ax*by - ay*bx;
	};
	long long area = 0;
	for(int i=0;i<n;i++) area += cmp(pts[i], pts[(i+1)%n]);
	if(area < 0) reverse(pts.begin(), pts.end());
	debug(pts);
	vector<pair<pair<int, bool>, pair<int, int> > > events;
	for(int i=0;i<n;i++)
	{
		if(pts[i].first != pts[(i+1)%n].first) continue;
		pair<pair<int, bool>, pair<int, int> > toAdd;
		if(pts[i].second < pts[(i+1)%n].second)
		{toAdd.second = make_pair(pts[i].second, pts[(i+1)%n].second);}
		else toAdd.second = make_pair(pts[(i+1)%n].second, pts[i].second);
		if(pts[i].second < pts[(i+1)%n].second) toAdd.first.second = 1;
		if(pts[i].second > pts[(i+1)%n].second) toAdd.first.second = 0;
		toAdd.first.first = pts[i].first;
		events.push_back(toAdd);
	}
	sort(events.begin(), events.end());
	result = events[0].first.first;
	int prev = -1;
	for(auto& v : events)
	{
		debug(v);
		debug(segs[0]);
		debug(segs[1]);
		if(prev != v.first.first)
		{
			if(np[0] != 0 || np[1] != 0) break;
			if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)^1].size() == 0) 
				{result = v.first.first;}
			else if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)].size() == 0) 
				result = v.first.first-1;	
		}
		if(v.first.second == 0) add(v.first.first, v.second.first, v.second.second);
		if(v.first.second == 1) sub(v.first.first, v.second.first, v.second.second);
	//	if(&v == &events[events.size()-1]) continue;
	//	if((*(&v + 1)).first.first != v.first.first)
	//		if(np[0] == 0 && np[1] == 0 && segs[(v.first.first+1)%2].size() == 0)
				prev = v.first.first;
	}
//	if(np[0] == 0 && np[1] == 0 && segs[0].size() == 0 && segs[1].size() == 0) result = m+1;
	cout<<result;
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 25 / 25
• Subtask 7: 0 / 10