oj.uz

Submission #886606

# Submission time Handle Problem Language Result Execution time Memory
886606 2023-12-12T12:01:18 Z Kel_Mahmut Towers (NOI22_towers) C++14
18 / 100
 1702 ms 169344 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> 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);
	}
	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 = 0; i < maxn; i++){
		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 20 ms 47196 KB Output is correct
2 Correct 16 ms 47192 KB Output is correct
3 Correct 17 ms 47196 KB Output is correct
4 Correct 16 ms 47196 KB Output is correct
5 Correct 16 ms 47196 KB Output is correct
6 Correct 15 ms 47196 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 16 ms 47192 KB Output is correct
9 Correct 17 ms 47196 KB Output is correct
10 Correct 15 ms 47196 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47196 KB Output is correct
2 Correct 16 ms 47192 KB Output is correct
3 Correct 17 ms 47196 KB Output is correct
4 Correct 16 ms 47196 KB Output is correct
5 Correct 16 ms 47196 KB Output is correct
6 Correct 15 ms 47196 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 16 ms 47192 KB Output is correct
9 Correct 17 ms 47196 KB Output is correct
10 Correct 15 ms 47196 KB Output is correct
11 Correct 16 ms 47196 KB Output is correct
12 Correct 15 ms 47196 KB Output is correct
13 Correct 17 ms 47260 KB Output is correct
14 Correct 18 ms 47420 KB Output is correct
15 Correct 16 ms 47196 KB Output is correct
16 Incorrect 16 ms 47292 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 65 ms 54208 KB Output is correct
2 Correct 76 ms 55632 KB Output is correct
3 Correct 338 ms 72020 KB Output is correct
4 Correct 632 ms 96624 KB Output is correct
5 Correct 128 ms 56404 KB Output is correct
6 Correct 30 ms 49236 KB Output is correct
7 Correct 397 ms 93428 KB Output is correct
8 Correct 380 ms 78928 KB Output is correct
9 Correct 538 ms 115688 KB Output is correct
10 Correct 495 ms 104616 KB Output is correct
11 Correct 820 ms 119208 KB Output is correct
12 Correct 790 ms 118960 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 169344 KB Output is correct
2 Correct 1604 ms 169060 KB Output is correct
3 Correct 1702 ms 168980 KB Output is correct
4 Correct 1664 ms 169224 KB Output is correct
5 Correct 1647 ms 168964 KB Output is correct
6 Correct 1293 ms 163908 KB Output is correct
7 Correct 1325 ms 164116 KB Output is correct
8 Correct 1293 ms 164116 KB Output is correct
9 Correct 1342 ms 163924 KB Output is correct
10 Correct 1325 ms 164136 KB Output is correct

Subtask #5
0 / 31.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

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