Submission #1005217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005217		emptypringlescan	Tiles (BOI24_tiles)	C++17	40 / 100	73 ms	7756 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	pair<int,int> arr[n];
	for(int i=0; i<n; i++) cin >> arr[i].first >> arr[i].second;
	vector<pair<int,pair<int,int> > > vert;
	for(int i=0; i<n-1; i++){
		if(arr[i].first==arr[i+1].first) vert.push_back({arr[i].first,{arr[i].second,arr[i+1].second}});
	}
	if(arr[0].first==arr[n-1].first) vert.push_back({arr[0].first,{arr[0].second,arr[n-1].second}});
	set<pair<int,int> > odd,even,all;
	set<pair<int,int> >::iterator it;
	sort(vert.begin(),vert.end());
	int ans=0,bad=0;
	for(int o=0; o<(int)vert.size(); o++){
		pair<int,pair<int,int> > i=vert[o];
		pair<int,int> ln=i.second;
		if(ln.second<ln.first) swap(ln.second,ln.first);
		it=all.upper_bound({ln.first,1e9});
		if(it!=all.begin()) it--;
		if(it!=all.end()&&it->first<=ln.first&&it->second>=ln.second){
			pair<int,int> tmp=*it;
			if((it->second-it->first)%2) bad--;
			all.erase(it);
			if(tmp.first<ln.first) all.insert({tmp.first,ln.first});
			if(ln.second<tmp.second) all.insert({ln.second,tmp.second});
			if((ln.first-tmp.first)%2) bad++;
			if((tmp.second-ln.second)%2) bad++;
		}
		else{
			it=all.lower_bound(ln);
			if(it!=all.end()&&it->first==ln.second){
				ln.second=it->second;
				if((it->second-it->first)%2) bad--;
				all.erase(it);
			}
			it=all.lower_bound(ln);
			if(it!=all.begin()) it--;
			if(it!=all.end()&&it->second==ln.first){
				ln.first=it->first;
				if((it->second-it->first)%2) bad--;
				all.erase(it);
			}
			all.insert(ln);
			if((ln.second-ln.first)%2) bad++;
		}
		if(o==(int)vert.size()-1||vert[o+1].first!=vert[o].first){
			if(bad>0){
				cout << ans;
				return 0;
			}
		}
		bool got=false;
		it=odd.lower_bound(ln);
		if(it!=odd.begin()) it--;
		vector<pair<int,int> > die;
		for(;it!=odd.end();it++){
			if(it->second<=ln.first) continue;
			if(it->first>=ln.second) break;
			if(i.first%2==0){
				cout << ans;
				return 0;
			}
			got=true;
			pair<int,int> tmp=*it;
			die.push_back(tmp);
			if(tmp.first<ln.first) odd.insert({tmp.first,ln.first});
			if(tmp.second>ln.second)odd.insert({ln.second,tmp.second});
		}
		for(auto j:die) odd.erase(j);
		die.clear();
		it=even.lower_bound(ln);
		if(it!=even.begin()) it--;
		for(;it!=even.end();it++){
			if(it->second<=ln.first) continue;
			if(it->first>=ln.second) break;
			if(i.first%2==1){
				cout << ans;
				return 0;
			}
			got=true;
			pair<int,int> tmp=*it;
			die.push_back(tmp);
			if(tmp.first<ln.first) even.insert({tmp.first,ln.first});
			if(tmp.second>ln.second)even.insert({ln.second,tmp.second});
		}
		for(auto j:die) even.erase(j);
		die.clear();
		if(!got){
			if(i.first%2==1) odd.insert(ln);
			else even.insert(ln);
		}
		if(i.first%2==1&&even.empty()){
			if(o==(int)vert.size()-1||vert[o+1].first!=vert[o].first) ans=i.first;
			if(o!=(int)vert.size()-1&&vert[o+1].first!=vert[o].first){
				if(vert[o+1].first%2==1) ans=vert[o+1].first;
				else ans=vert[o+1].first-1;
			}
		}
		else if(i.first%2==0&&odd.empty()){
			if(o==(int)vert.size()-1||vert[o+1].first!=vert[o].first) ans=i.first;
			if(o!=(int)vert.size()-1&&vert[o+1].first!=vert[o].first){
				if(vert[o+1].first%2==0) ans=vert[o+1].first;
				else ans=vert[o+1].first-1;
			}
		}
	}
	cout << ans;
	
}
/*18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4
*/

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