oj.uz

Submission #949824

# Submission time Handle Problem Language Result Execution time Memory
949824 2024-03-19T18:18:55 Z esomer Towers (NOI22_towers) C++17
11 / 100
 848 ms 179776 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxX = 1e6;

vector<int> cols[maxX + 1], rows[maxX + 1];
vector<bool> chosen[maxX + 1];
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] = (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]--;
				if(ind[row] >= 0) choose(rows[row][ind[row]], 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 90452 KB Output is correct
2 Correct 29 ms 90460 KB Output is correct
3 Correct 32 ms 90460 KB Output is correct
4 Correct 30 ms 90472 KB Output is correct
5 Correct 30 ms 90460 KB Output is correct
6 Correct 33 ms 90460 KB Output is correct
7 Correct 30 ms 90264 KB Output is correct
8 Correct 30 ms 90456 KB Output is correct
9 Correct 29 ms 90476 KB Output is correct
10 Correct 29 ms 90456 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 90452 KB Output is correct
2 Correct 29 ms 90460 KB Output is correct
3 Correct 32 ms 90460 KB Output is correct
4 Correct 30 ms 90472 KB Output is correct
5 Correct 30 ms 90460 KB Output is correct
6 Correct 33 ms 90460 KB Output is correct
7 Correct 30 ms 90264 KB Output is correct
8 Correct 30 ms 90456 KB Output is correct
9 Correct 29 ms 90476 KB Output is correct
10 Correct 29 ms 90456 KB Output is correct
11 Correct 30 ms 90300 KB Output is correct
12 Correct 30 ms 90464 KB Output is correct
13 Correct 32 ms 90456 KB Output is correct
14 Correct 30 ms 90276 KB Output is correct
15 Correct 30 ms 90460 KB Output is correct
16 Incorrect 30 ms 90460 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 93024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 165924 KB Output is correct
2 Correct 453 ms 165516 KB Output is correct
3 Correct 457 ms 165712 KB Output is correct
4 Correct 424 ms 165764 KB Output is correct
5 Correct 436 ms 165764 KB Output is correct
6 Correct 821 ms 179776 KB Output is correct
7 Correct 793 ms 179512 KB Output is correct
8 Correct 802 ms 179480 KB Output is correct
9 Correct 802 ms 179352 KB Output is correct
10 Correct 848 ms 179516 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 90452 KB Output is correct
2 Correct 29 ms 90460 KB Output is correct
3 Correct 32 ms 90460 KB Output is correct
4 Correct 30 ms 90472 KB Output is correct
5 Correct 30 ms 90460 KB Output is correct
6 Correct 33 ms 90460 KB Output is correct
7 Correct 30 ms 90264 KB Output is correct
8 Correct 30 ms 90456 KB Output is correct
9 Correct 29 ms 90476 KB Output is correct
10 Correct 29 ms 90456 KB Output is correct
11 Correct 30 ms 90300 KB Output is correct
12 Correct 30 ms 90464 KB Output is correct
13 Correct 32 ms 90456 KB Output is correct
14 Correct 30 ms 90276 KB Output is correct
15 Correct 30 ms 90460 KB Output is correct
16 Incorrect 30 ms 90460 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 90452 KB Output is correct
2 Correct 29 ms 90460 KB Output is correct
3 Correct 32 ms 90460 KB Output is correct
4 Correct 30 ms 90472 KB Output is correct
5 Correct 30 ms 90460 KB Output is correct
6 Correct 33 ms 90460 KB Output is correct
7 Correct 30 ms 90264 KB Output is correct
8 Correct 30 ms 90456 KB Output is correct
9 Correct 29 ms 90476 KB Output is correct
10 Correct 29 ms 90456 KB Output is correct
11 Correct 30 ms 90300 KB Output is correct
12 Correct 30 ms 90464 KB Output is correct
13 Correct 32 ms 90456 KB Output is correct
14 Correct 30 ms 90276 KB Output is correct
15 Correct 30 ms 90460 KB Output is correct
16 Incorrect 30 ms 90460 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 90452 KB Output is correct
2 Correct 29 ms 90460 KB Output is correct
3 Correct 32 ms 90460 KB Output is correct
4 Correct 30 ms 90472 KB Output is correct
5 Correct 30 ms 90460 KB Output is correct
6 Correct 33 ms 90460 KB Output is correct
7 Correct 30 ms 90264 KB Output is correct
8 Correct 30 ms 90456 KB Output is correct
9 Correct 29 ms 90476 KB Output is correct
10 Correct 29 ms 90456 KB Output is correct
11 Correct 30 ms 90300 KB Output is correct
12 Correct 30 ms 90464 KB Output is correct
13 Correct 32 ms 90456 KB Output is correct
14 Correct 30 ms 90276 KB Output is correct
15 Correct 30 ms 90460 KB Output is correct
16 Incorrect 30 ms 90460 KB Output isn't correct
17 Halted 0 ms 0 KB -