oj.uz

Submission #886602

# Submission time Handle Problem Language Result Execution time Memory
886602 2023-12-12T11:51:07 Z Kel_Mahmut Towers (NOI22_towers) C++17
18 / 100
 1730 ms 169364 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){
		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 16 ms 47316 KB Output is correct
2 Correct 16 ms 47412 KB Output is correct
3 Correct 16 ms 47232 KB Output is correct
4 Correct 16 ms 47196 KB Output is correct
5 Correct 16 ms 47196 KB Output is correct
6 Correct 16 ms 47264 KB Output is correct
7 Correct 15 ms 47416 KB Output is correct
8 Correct 15 ms 47196 KB Output is correct
9 Correct 16 ms 47420 KB Output is correct
10 Correct 18 ms 47192 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 47316 KB Output is correct
2 Correct 16 ms 47412 KB Output is correct
3 Correct 16 ms 47232 KB Output is correct
4 Correct 16 ms 47196 KB Output is correct
5 Correct 16 ms 47196 KB Output is correct
6 Correct 16 ms 47264 KB Output is correct
7 Correct 15 ms 47416 KB Output is correct
8 Correct 15 ms 47196 KB Output is correct
9 Correct 16 ms 47420 KB Output is correct
10 Correct 18 ms 47192 KB Output is correct
11 Correct 16 ms 47196 KB Output is correct
12 Correct 16 ms 47180 KB Output is correct
13 Correct 16 ms 47196 KB Output is correct
14 Correct 16 ms 47192 KB Output is correct
15 Correct 15 ms 47192 KB Output is correct
16 Incorrect 16 ms 47196 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 64 ms 54092 KB Output is correct
2 Correct 82 ms 55536 KB Output is correct
3 Correct 331 ms 72024 KB Output is correct
4 Correct 633 ms 96508 KB Output is correct
5 Correct 130 ms 56600 KB Output is correct
6 Correct 28 ms 49244 KB Output is correct
7 Correct 383 ms 93524 KB Output is correct
8 Correct 378 ms 78860 KB Output is correct
9 Correct 551 ms 115796 KB Output is correct
10 Correct 482 ms 104536 KB Output is correct
11 Correct 824 ms 118944 KB Output is correct
12 Correct 790 ms 118688 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1686 ms 169072 KB Output is correct
2 Correct 1709 ms 169364 KB Output is correct
3 Correct 1679 ms 169180 KB Output is correct
4 Correct 1698 ms 169148 KB Output is correct
5 Correct 1730 ms 168996 KB Output is correct
6 Correct 1316 ms 162596 KB Output is correct
7 Correct 1298 ms 162620 KB Output is correct
8 Correct 1299 ms 162852 KB Output is correct
9 Correct 1293 ms 162816 KB Output is correct
10 Correct 1312 ms 162844 KB Output is correct

Subtask #5
0 / 31.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

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