Submission #949841

#	Time	Username	Problem	Language	Result	Execution time	Memory
949841		esomer	Towers (NOI22_towers)	C++17	11 / 100	827 ms	177108 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxX = 1e6;
 
vector<int> cols[maxX + 1], rows[maxX + 1];
vector<bool> chosen[maxX + 1];
pair<int, int> ind[maxX + 1];
 
bool choose(int X, int Y){
	int lo = 0;
	int hi = (int)cols[X].size() - 1;
	int bst = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(cols[X][mid] >= Y){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	if(chosen[X][bst]) return true;
	chosen[X][bst] = true;
	return false;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N; cin >> N;
	vector<pair<int, int>> A(N);
	for(int i = 0; i < N; i++){
		int X, Y; cin >> X >> Y;
		A[i] = {X, Y};
		cols[X].push_back(Y);
		rows[Y].push_back(X);
	}
	for(int i = 1; i <= maxX; i++){
		sort(rows[i].begin(), rows[i].end());
		sort(cols[i].begin(), cols[i].end());
		ind[i] = {0, (int)rows[i].size() - 1};
		chosen[i].assign((int)cols[i].size(), false);
	}
	for(int i = 1; i <= maxX; i++){
		if((int)rows[i].size() > 0){
			choose(rows[i][0], i);
			choose(rows[i].back(), i);
		}
	}
	for(int i = maxX; i >= 1; i--){
		int f = -1, s = -1;
		for(int j = 0; j < (int)cols[i].size(); j++){
			if(chosen[i][j]){
				if(f == -1) f = j;
				s = j;
			}
		}
		for(int j = f + 1; j < s; j++){
			if(chosen[i][j]){
				int row = cols[i][j];
				ind[row].second--;
				if(ind[row].second > 0) choose(rows[row][ind[row].second], row);
				chosen[i][j] = false;
			}
		}
	}
	for(int i = 1; i <= maxX; i++){
		int f = -1, s = -1;
		for(int j = 0; j < (int)cols[i].size(); j++){
			if(chosen[i][j]){
				if(f == -1) f = j;
				s = j;
			}
		}
		for(int j = f + 1; j < s; j++){
			if(chosen[i][j]){
				int row = cols[i][j];
				ind[row].first++;
				if(ind[row].first < ind[row].second) choose(rows[row][ind[row].first], row);
				chosen[i][j] = false;
			}
		}
	}
	for(int i = 0; i < N; i++){
		if(choose(A[i].first, A[i].second)) cout << 1;
		else cout << 0;
	}
	cout << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19