Submission #950585

#	Time	Username	Problem	Language	Result	Execution time	Memory
950585		esomer	Towers (NOI22_towers)	C++17	100 / 100	897 ms	191272 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> indRow[maxX + 1], indCol[maxX + 1];
queue<pair<int, int>> q;
 
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;
	// cout << "Chose " << X << " " << cols[X][bst] << " bst " << bst << " indCol " << indCol[X].first << " " << indCol[X].second << "\n";
	chosen[X][bst] = true;
	if(indCol[X].first == -1){
		indCol[X] = {bst, bst};
	}else if(indCol[X].first == indCol[X].second){
		indCol[X] = {min(bst, indCol[X].first), max(bst, indCol[X].second)};
	}else if(indCol[X].first > bst){
		// cout << "Add " << X << " " << indCol[X].first << "\n";
		q.push({X, indCol[X].first});
		indCol[X].first = bst;
	}else if(indCol[X].second < bst){
		q.push({X, indCol[X].second});
		// cout << "Add " << X << " " << indCol[X].second << "\n";
		indCol[X].second = bst;
	}else{
		q.push({X, bst});
	}
	// cout << "After indCol " << indCol[X].first << " " << indCol[X].second << "\n";
	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());
		indRow[i] = {0, (int)rows[i].size() - 1};
		indCol[i] = {-1, -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);
		}
	}
	while(!q.empty()){
		int X = q.front().first; int i = q.front().second; q.pop();
		// cout << "Erased: " << X << " " << cols[X][i] << "\n";
		chosen[X][i] = false;
		int row = cols[X][i];
		if(rows[row][indRow[row].second] == X){
			indRow[row].second--;
			if(indRow[row].second > indRow[row].first) choose(rows[row][indRow[row].second], row);
		}
		if(rows[row][indRow[row].first] == X){
			indRow[row].first++;
			if(indRow[row].first < indRow[row].second) choose(rows[row][indRow[row].first], row);
		}
	}
	// cout << "-----\n";
	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: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 31 / 31
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19