Submission #886599

#TimeUsernameProblemLanguageResultExecution timeMemory
886599Kel_MahmutTowers (NOI22_towers)C++17
0 / 100
1676 ms169412 KiB
#include <bits/stdc++.h> #define pb push_back #define all(aa) aa.begin(), aa.end() using namespace std; constexpr int maxn = 1e6; 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 >= 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; vis[ index[{i, x_col.back()}] ] = 1; // cout << index[{i, x_col[0]}] << ' ' << index[{i, x_col.back()}] << endl; Y_act[x_col[0]].pb({i, -1}); Y_act[x_col.back()].pb({i, 1}); sort(all(Y_act[x_col[0]])); sort(all(Y_act[x_col.back()])); fix(x_col[0]); fix(x_col.back()); } for(int i = 0; i < n; i++){ cout << (vis[i] ? 1 : 0); } }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    if(y_nxt >= X_vals[to_fix[0]].size())
      |       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...