oj.uz

Submission #931953

# Submission time Handle Problem Language Result Execution time Memory
931953 2024-02-22T16:01:20 Z d4xn Towers (NOI22_towers) C++17
11 / 100
 1635 ms 227812 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";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97056 KB Output is correct
2 Correct 28 ms 96856 KB Output is correct
3 Correct 29 ms 97028 KB Output is correct
4 Correct 28 ms 96860 KB Output is correct
5 Correct 32 ms 97144 KB Output is correct
6 Correct 33 ms 96860 KB Output is correct
7 Correct 29 ms 96988 KB Output is correct
8 Correct 29 ms 96856 KB Output is correct
9 Correct 29 ms 96860 KB Output is correct
10 Correct 30 ms 96960 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97056 KB Output is correct
2 Correct 28 ms 96856 KB Output is correct
3 Correct 29 ms 97028 KB Output is correct
4 Correct 28 ms 96860 KB Output is correct
5 Correct 32 ms 97144 KB Output is correct
6 Correct 33 ms 96860 KB Output is correct
7 Correct 29 ms 96988 KB Output is correct
8 Correct 29 ms 96856 KB Output is correct
9 Correct 29 ms 96860 KB Output is correct
10 Correct 30 ms 96960 KB Output is correct
11 Correct 30 ms 96856 KB Output is correct
12 Correct 30 ms 96856 KB Output is correct
13 Incorrect 29 ms 97112 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 102056 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 1548 ms 209724 KB Output is correct
2 Correct 1635 ms 209664 KB Output is correct
3 Correct 1584 ms 209660 KB Output is correct
4 Correct 1617 ms 209712 KB Output is correct
5 Correct 1576 ms 209724 KB Output is correct
6 Correct 987 ms 227768 KB Output is correct
7 Correct 967 ms 226900 KB Output is correct
8 Correct 960 ms 227812 KB Output is correct
9 Correct 958 ms 226884 KB Output is correct
10 Correct 986 ms 227468 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97056 KB Output is correct
2 Correct 28 ms 96856 KB Output is correct
3 Correct 29 ms 97028 KB Output is correct
4 Correct 28 ms 96860 KB Output is correct
5 Correct 32 ms 97144 KB Output is correct
6 Correct 33 ms 96860 KB Output is correct
7 Correct 29 ms 96988 KB Output is correct
8 Correct 29 ms 96856 KB Output is correct
9 Correct 29 ms 96860 KB Output is correct
10 Correct 30 ms 96960 KB Output is correct
11 Correct 30 ms 96856 KB Output is correct
12 Correct 30 ms 96856 KB Output is correct
13 Incorrect 29 ms 97112 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97056 KB Output is correct
2 Correct 28 ms 96856 KB Output is correct
3 Correct 29 ms 97028 KB Output is correct
4 Correct 28 ms 96860 KB Output is correct
5 Correct 32 ms 97144 KB Output is correct
6 Correct 33 ms 96860 KB Output is correct
7 Correct 29 ms 96988 KB Output is correct
8 Correct 29 ms 96856 KB Output is correct
9 Correct 29 ms 96860 KB Output is correct
10 Correct 30 ms 96960 KB Output is correct
11 Correct 30 ms 96856 KB Output is correct
12 Correct 30 ms 96856 KB Output is correct
13 Incorrect 29 ms 97112 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97056 KB Output is correct
2 Correct 28 ms 96856 KB Output is correct
3 Correct 29 ms 97028 KB Output is correct
4 Correct 28 ms 96860 KB Output is correct
5 Correct 32 ms 97144 KB Output is correct
6 Correct 33 ms 96860 KB Output is correct
7 Correct 29 ms 96988 KB Output is correct
8 Correct 29 ms 96856 KB Output is correct
9 Correct 29 ms 96860 KB Output is correct
10 Correct 30 ms 96960 KB Output is correct
11 Correct 30 ms 96856 KB Output is correct
12 Correct 30 ms 96856 KB Output is correct
13 Incorrect 29 ms 97112 KB Output isn't correct
14 Halted 0 ms 0 KB -