oj.uz

Submission #886732

# Submission time Handle Problem Language Result Execution time Memory
886732 2023-12-12T18:11:48 Z Kel_Mahmut Towers (NOI22_towers) C++17
18 / 100
 1895 ms 183024 KB 
#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
using namespace std;

constexpr int maxn = 1e6 + 5;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> X_vals(maxn);
	map<pair<int, int>, int> index;
	vector<vector<pair<int, int>>> Y_act(maxn); // cord, type (1 if it is upper bound, -1 if lower bound)
	vector<int> point;
	vector<int> vis(n);
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		--x, --y;
		index[{x, y}] = i;
		X_vals[x].pb(y);
		point.pb(x);
	}
	for(int i = 0; i < maxn; i++){
		if(!X_vals[i].empty())
			sort(all(X_vals[i]));
	}

	function<void(int)> fix = [&](int y){

		sort(all(Y_act[y]));

		Y_act[y].resize(unique(all(Y_act[y]), [&](pair<int, int> a, pair<int, int> b){
			return a.first == b.first;
		}) - Y_act[y].begin());

		if(Y_act[y].size() <= 2){
			return;
		}

		// ayni y-de 3 tane nokta var
		sort(all(Y_act[y]));
		swap(Y_act[y][2], Y_act[y][1]);
		array<int, 3> to_fix = {Y_act[y][2].first, y, Y_act[y][2].second};
		Y_act[y].resize(2);
		vis[   index[{to_fix[0], to_fix[1]}]   ] = 0;

		if(to_fix[2] == 1){
			int y_nxt = (lower_bound(all(X_vals[to_fix[0]] ), to_fix[1]) - X_vals[to_fix[0]].begin() ) - 1;
			
			if(y_nxt < 0) 
				return;

			if(vis[  index[{to_fix[0], y_nxt}]  ])
				return;

			vis[  index[{to_fix[0], y_nxt}]  ] = 1;
			Y_act[  y_nxt ].pb({to_fix[0], 1});

			fix(y_nxt);
		}

		if(to_fix[2] == -1){
			int y_nxt = (lower_bound(all(X_vals[to_fix[0]] ), to_fix[1])  - X_vals[to_fix[0]].begin() ) + 1;
			
			if(y_nxt >= (int) X_vals[to_fix[0]].size())
				return;

			if(vis[  index[{to_fix[0], y_nxt}]  ])
				return;

			vis[  index[{to_fix[0], y_nxt}]  ] = 1;
			Y_act[  y_nxt ].pb({to_fix[0], -1});

			fix(y_nxt);
		}
	};

	for(int i : point){
		if(X_vals[i].empty()) continue;	

		vector<int> x_col = X_vals[i];

		
		vis[  index[{i, x_col[0]}]  ] = 1;
		Y_act[x_col[0]].pb({i, -1});
		sort(all(Y_act[x_col[0]]));
		fix(x_col[0]);

		// if(vis[ index[{i, x_col.back()}]]) continue;
		vis[  index[{i, x_col.back()}]  ] = 1;
		// cout << index[{i, x_col[0]}] << ' ' << index[{i, x_col.back()}] << endl;
		
		
		Y_act[x_col.back()].pb({i, 1});

		
		sort(all(Y_act[x_col.back()]));

		
		fix(x_col.back());

	}

	for(int i = 0; i < n; i++){
		cout << (vis[i] ? 1 : 0);
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47196 KB Output is correct
2 Correct 15 ms 47196 KB Output is correct
3 Correct 14 ms 47196 KB Output is correct
4 Correct 14 ms 47280 KB Output is correct
5 Correct 15 ms 47260 KB Output is correct
6 Correct 13 ms 47196 KB Output is correct
7 Correct 14 ms 47192 KB Output is correct
8 Correct 14 ms 47196 KB Output is correct
9 Correct 15 ms 47424 KB Output is correct
10 Correct 14 ms 47196 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47196 KB Output is correct
2 Correct 15 ms 47196 KB Output is correct
3 Correct 14 ms 47196 KB Output is correct
4 Correct 14 ms 47280 KB Output is correct
5 Correct 15 ms 47260 KB Output is correct
6 Correct 13 ms 47196 KB Output is correct
7 Correct 14 ms 47192 KB Output is correct
8 Correct 14 ms 47196 KB Output is correct
9 Correct 15 ms 47424 KB Output is correct
10 Correct 14 ms 47196 KB Output is correct
11 Correct 14 ms 47196 KB Output is correct
12 Correct 14 ms 47424 KB Output is correct
13 Correct 14 ms 47196 KB Output is correct
14 Correct 14 ms 47192 KB Output is correct
15 Correct 14 ms 47192 KB Output is correct
16 Incorrect 14 ms 47192 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 55260 KB Output is correct
2 Correct 94 ms 56776 KB Output is correct
3 Correct 385 ms 75664 KB Output is correct
4 Correct 757 ms 103356 KB Output is correct
5 Correct 150 ms 57796 KB Output is correct
6 Correct 35 ms 49496 KB Output is correct
7 Correct 546 ms 100712 KB Output is correct
8 Correct 467 ms 83228 KB Output is correct
9 Correct 921 ms 125792 KB Output is correct
10 Correct 690 ms 113476 KB Output is correct
11 Correct 1065 ms 129068 KB Output is correct
12 Correct 1037 ms 128740 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1892 ms 183024 KB Output is correct
2 Correct 1880 ms 182732 KB Output is correct
3 Correct 1882 ms 182768 KB Output is correct
4 Correct 1863 ms 182904 KB Output is correct
5 Correct 1895 ms 182860 KB Output is correct
6 Correct 1526 ms 181548 KB Output is correct
7 Correct 1502 ms 181776 KB Output is correct
8 Correct 1559 ms 181776 KB Output is correct
9 Correct 1507 ms 181952 KB Output is correct
10 Correct 1569 ms 181804 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47196 KB Output is correct
2 Correct 15 ms 47196 KB Output is correct
3 Correct 14 ms 47196 KB Output is correct
4 Correct 14 ms 47280 KB Output is correct
5 Correct 15 ms 47260 KB Output is correct
6 Correct 13 ms 47196 KB Output is correct
7 Correct 14 ms 47192 KB Output is correct
8 Correct 14 ms 47196 KB Output is correct
9 Correct 15 ms 47424 KB Output is correct
10 Correct 14 ms 47196 KB Output is correct
11 Correct 14 ms 47196 KB Output is correct
12 Correct 14 ms 47424 KB Output is correct
13 Correct 14 ms 47196 KB Output is correct
14 Correct 14 ms 47192 KB Output is correct
15 Correct 14 ms 47192 KB Output is correct
16 Incorrect 14 ms 47192 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47196 KB Output is correct
2 Correct 15 ms 47196 KB Output is correct
3 Correct 14 ms 47196 KB Output is correct
4 Correct 14 ms 47280 KB Output is correct
5 Correct 15 ms 47260 KB Output is correct
6 Correct 13 ms 47196 KB Output is correct
7 Correct 14 ms 47192 KB Output is correct
8 Correct 14 ms 47196 KB Output is correct
9 Correct 15 ms 47424 KB Output is correct
10 Correct 14 ms 47196 KB Output is correct
11 Correct 14 ms 47196 KB Output is correct
12 Correct 14 ms 47424 KB Output is correct
13 Correct 14 ms 47196 KB Output is correct
14 Correct 14 ms 47192 KB Output is correct
15 Correct 14 ms 47192 KB Output is correct
16 Incorrect 14 ms 47192 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47196 KB Output is correct
2 Correct 15 ms 47196 KB Output is correct
3 Correct 14 ms 47196 KB Output is correct
4 Correct 14 ms 47280 KB Output is correct
5 Correct 15 ms 47260 KB Output is correct
6 Correct 13 ms 47196 KB Output is correct
7 Correct 14 ms 47192 KB Output is correct
8 Correct 14 ms 47196 KB Output is correct
9 Correct 15 ms 47424 KB Output is correct
10 Correct 14 ms 47196 KB Output is correct
11 Correct 14 ms 47196 KB Output is correct
12 Correct 14 ms 47424 KB Output is correct
13 Correct 14 ms 47196 KB Output is correct
14 Correct 14 ms 47192 KB Output is correct
15 Correct 14 ms 47192 KB Output is correct
16 Incorrect 14 ms 47192 KB Output isn't correct
17 Halted 0 ms 0 KB -