Submission #931954

#	Time	Username	Problem	Language	Result	Execution time	Memory
931954		d4xn	Towers (NOI22_towers)	C++17	11 / 100	1180 ms	206228 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 1e6+6;

int n, x[N], y[N];
set<int> sx[N], sy[N];
vector<pair<int, int>> s;

void prop(int a, int b) {
  auto it = sx[a].upper_bound(b);
  if (it != sx[a].end()) {
    sy[*it].insert(a);
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    sx[x[i]].insert(y[i]);
  }
  
  for (int i = 0; i < N; i++) {
    int sz = sx[i].size();
    
    if (!sz) continue;
    else if (sz == 1) {
      sy[*sx[i].begin()].insert(i);
    }
    else {
      int a = *sx[i].begin();
      int b = *prev(sx[i].end());
      
      sx[i].clear();
      sx[i].insert(a);
      sx[i].insert(b);
      
      sy[a].insert(i);
      sy[b].insert(i);
    }
  }
  
  for (int i = 0; i < N; i++) {
    int sz = sy[i].size();
    if (sz <= 2) continue;
    else {
      int a = *sy[i].begin();
      int b = *prev(sy[i].end());
    
      for (int j : sy[i]) {
        if (a < j && j < b) {
          prop(j, i);
          //sx[j].erase(i);
        }
      }
      
      sy[i].clear();
      sy[i].insert(a);
      sy[i].insert(b);
    }
  }
  
  for (int i = 0; i < N; i++) {
    for (int j : sx[i]) {
      //cout << "a -> " << i << " " << j << endl;
      //s.push_back(make_pair(i, j));
    }
    for (int j : sy[i]) {
      //cout << "b -> " << i << " " << j << endl;
      s.push_back(make_pair(j, i));
    }
  }
  sort(all(s));
  
  for (int i = 0; i < n; i++) {
    if (binary_search(all(s), make_pair(x[i], y[i]))) {
      cout << 1;
    }
    else {
      cout << 0;
    }
  }
  cout << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:14: warning: unused variable 'j' [-Wunused-variable]
   69 |     for (int j : sx[i]) {
      |              ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19