oj.uz

Submission #931954

# Submission time Handle Problem Language Result Execution time Memory
931954 2024-02-22T16:02:32 Z d4xn Towers (NOI22_towers) C++17
11 / 100
 1180 ms 206228 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 96860 KB Output is correct
2 Correct 27 ms 97032 KB Output is correct
3 Correct 27 ms 96860 KB Output is correct
4 Correct 27 ms 96856 KB Output is correct
5 Correct 27 ms 96860 KB Output is correct
6 Correct 30 ms 96860 KB Output is correct
7 Correct 28 ms 96860 KB Output is correct
8 Correct 28 ms 96860 KB Output is correct
9 Correct 27 ms 96860 KB Output is correct
10 Correct 28 ms 96860 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 96860 KB Output is correct
2 Correct 27 ms 97032 KB Output is correct
3 Correct 27 ms 96860 KB Output is correct
4 Correct 27 ms 96856 KB Output is correct
5 Correct 27 ms 96860 KB Output is correct
6 Correct 30 ms 96860 KB Output is correct
7 Correct 28 ms 96860 KB Output is correct
8 Correct 28 ms 96860 KB Output is correct
9 Correct 27 ms 96860 KB Output is correct
10 Correct 28 ms 96860 KB Output is correct
11 Correct 27 ms 96860 KB Output is correct
12 Correct 27 ms 96860 KB Output is correct
13 Incorrect 29 ms 96860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 101468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 196904 KB Output is correct
2 Correct 1134 ms 196952 KB Output is correct
3 Correct 1180 ms 196936 KB Output is correct
4 Correct 1148 ms 196900 KB Output is correct
5 Correct 1147 ms 196900 KB Output is correct
6 Correct 815 ms 205456 KB Output is correct
7 Correct 791 ms 205248 KB Output is correct
8 Correct 828 ms 206228 KB Output is correct
9 Correct 791 ms 205760 KB Output is correct
10 Correct 787 ms 205384 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 96860 KB Output is correct
2 Correct 27 ms 97032 KB Output is correct
3 Correct 27 ms 96860 KB Output is correct
4 Correct 27 ms 96856 KB Output is correct
5 Correct 27 ms 96860 KB Output is correct
6 Correct 30 ms 96860 KB Output is correct
7 Correct 28 ms 96860 KB Output is correct
8 Correct 28 ms 96860 KB Output is correct
9 Correct 27 ms 96860 KB Output is correct
10 Correct 28 ms 96860 KB Output is correct
11 Correct 27 ms 96860 KB Output is correct
12 Correct 27 ms 96860 KB Output is correct
13 Incorrect 29 ms 96860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 96860 KB Output is correct
2 Correct 27 ms 97032 KB Output is correct
3 Correct 27 ms 96860 KB Output is correct
4 Correct 27 ms 96856 KB Output is correct
5 Correct 27 ms 96860 KB Output is correct
6 Correct 30 ms 96860 KB Output is correct
7 Correct 28 ms 96860 KB Output is correct
8 Correct 28 ms 96860 KB Output is correct
9 Correct 27 ms 96860 KB Output is correct
10 Correct 28 ms 96860 KB Output is correct
11 Correct 27 ms 96860 KB Output is correct
12 Correct 27 ms 96860 KB Output is correct
13 Incorrect 29 ms 96860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 96860 KB Output is correct
2 Correct 27 ms 97032 KB Output is correct
3 Correct 27 ms 96860 KB Output is correct
4 Correct 27 ms 96856 KB Output is correct
5 Correct 27 ms 96860 KB Output is correct
6 Correct 30 ms 96860 KB Output is correct
7 Correct 28 ms 96860 KB Output is correct
8 Correct 28 ms 96860 KB Output is correct
9 Correct 27 ms 96860 KB Output is correct
10 Correct 28 ms 96860 KB Output is correct
11 Correct 27 ms 96860 KB Output is correct
12 Correct 27 ms 96860 KB Output is correct
13 Incorrect 29 ms 96860 KB Output isn't correct
14 Halted 0 ms 0 KB -