oj.uz

Submission #886603

# Submission time Handle Problem Language Result Execution time Memory
886603 2023-12-12T11:51:59 Z vjudge1 Towers (NOI22_towers) C++17
18 / 100
 1750 ms 169248 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 15 ms 47192 KB Output is correct
2 Correct 18 ms 47544 KB Output is correct
3 Correct 16 ms 47420 KB Output is correct
4 Correct 15 ms 47412 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 15 ms 47448 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 18 ms 47344 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 16 ms 47196 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47192 KB Output is correct
2 Correct 18 ms 47544 KB Output is correct
3 Correct 16 ms 47420 KB Output is correct
4 Correct 15 ms 47412 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 15 ms 47448 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 18 ms 47344 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 16 ms 47196 KB Output is correct
11 Correct 15 ms 47196 KB Output is correct
12 Correct 16 ms 47196 KB Output is correct
13 Correct 16 ms 47412 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 16 ms 47192 KB Output is correct
16 Incorrect 16 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 63 ms 54192 KB Output is correct
2 Correct 74 ms 55580 KB Output is correct
3 Correct 332 ms 72016 KB Output is correct
4 Correct 619 ms 96684 KB Output is correct
5 Correct 123 ms 56388 KB Output is correct
6 Correct 28 ms 49244 KB Output is correct
7 Correct 391 ms 93500 KB Output is correct
8 Correct 373 ms 78732 KB Output is correct
9 Correct 541 ms 115536 KB Output is correct
10 Correct 483 ms 104532 KB Output is correct
11 Correct 817 ms 118824 KB Output is correct
12 Correct 772 ms 118684 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1651 ms 169072 KB Output is correct
2 Correct 1651 ms 169024 KB Output is correct
3 Correct 1750 ms 169104 KB Output is correct
4 Correct 1674 ms 169248 KB Output is correct
5 Correct 1710 ms 169104 KB Output is correct
6 Correct 1306 ms 162532 KB Output is correct
7 Correct 1300 ms 162968 KB Output is correct
8 Correct 1324 ms 162540 KB Output is correct
9 Correct 1302 ms 162456 KB Output is correct
10 Correct 1274 ms 162504 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47192 KB Output is correct
2 Correct 18 ms 47544 KB Output is correct
3 Correct 16 ms 47420 KB Output is correct
4 Correct 15 ms 47412 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 15 ms 47448 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 18 ms 47344 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 16 ms 47196 KB Output is correct
11 Correct 15 ms 47196 KB Output is correct
12 Correct 16 ms 47196 KB Output is correct
13 Correct 16 ms 47412 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 16 ms 47192 KB Output is correct
16 Incorrect 16 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 47192 KB Output is correct
2 Correct 18 ms 47544 KB Output is correct
3 Correct 16 ms 47420 KB Output is correct
4 Correct 15 ms 47412 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 15 ms 47448 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 18 ms 47344 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 16 ms 47196 KB Output is correct
11 Correct 15 ms 47196 KB Output is correct
12 Correct 16 ms 47196 KB Output is correct
13 Correct 16 ms 47412 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 16 ms 47192 KB Output is correct
16 Incorrect 16 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 47192 KB Output is correct
2 Correct 18 ms 47544 KB Output is correct
3 Correct 16 ms 47420 KB Output is correct
4 Correct 15 ms 47412 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 15 ms 47448 KB Output is correct
7 Correct 16 ms 47196 KB Output is correct
8 Correct 18 ms 47344 KB Output is correct
9 Correct 16 ms 47192 KB Output is correct
10 Correct 16 ms 47196 KB Output is correct
11 Correct 15 ms 47196 KB Output is correct
12 Correct 16 ms 47196 KB Output is correct
13 Correct 16 ms 47412 KB Output is correct
14 Correct 18 ms 47192 KB Output is correct
15 Correct 16 ms 47192 KB Output is correct
16 Incorrect 16 ms 47192 KB Output isn't correct
17 Halted 0 ms 0 KB -