Submission #886732

#TimeUsernameProblemLanguageResultExecution timeMemory
886732Kel_MahmutTowers (NOI22_towers)C++17
18 / 100
1895 ms183024 KiB
#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); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...