oj.uz

Submission #1005191

# Submission time Handle Problem Language Result Execution time Memory
1005191 2024-06-22T08:35:32 Z emptypringlescan Tiles (BOI24_tiles) C++17
0 / 100
 51 ms 6856 KB 
#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;
			all.erase(it);
			if((it->second-it->first)%2) bad--;
			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--;
		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;
			odd.erase(it);
			odd.insert({max(tmp.first,ln.first),min(tmp.second,ln.second)});
			
		}
		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;
			even.erase(it);
			even.insert({max(tmp.first,ln.first),min(tmp.second,ln.second)});
			
		}
		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){
				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){
				if(vert[o+1].first%2==0) ans=vert[o+1].first;
				else ans=vert[o+1].first-1;
			}
		}
	}
	cout << ans;
	
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 6 ms 1184 KB Output is correct
3 Correct 47 ms 6856 KB Output is correct
4 Incorrect 37 ms 4044 KB Output isn't correct
5 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 24 ms 3540 KB Output is correct
6 Correct 41 ms 3664 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 51 ms 692 KB Output isn't correct
11 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 Incorrect 25 ms 4168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6856 KB Output is correct
2 Incorrect 29 ms 4040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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