oj.uz

Submission #886549

# Submission time Handle Problem Language Result Execution time Memory
886549 2023-12-12T10:06:18 Z vjudge1 Towers (NOI22_towers) C++17
11 / 100
 699 ms 129476 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B>
string to_string(pair<A, B>);
string to_string(string S) {
  return '"' + S + '"';
}
string to_string(const char* c) {
  return to_string(string(c));
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template<size_t T>
string to_string(bitset<T> bs) {
  return bs.to_string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  return res + "}";
}
template<typename T>
string to_string(T v) {
  string res = "{";
  for (auto e : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(e);
  }
  return res + "}";
}
template<typename A, typename B>
string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename H, typename... T>
void debug_out(H head, T... tail) {
  cerr << "  " << to_string(head);
  debug_out(tail...);
}

#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) 
#else 
  #define debug(...) void(37)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> X(N), Y(N);
  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> Y[i];
    --X[i], --Y[i];
  }
  #ifdef LOCAL
    const int MAX = int(30);
  #else
    const int MAX = int(1e6);
  #endif
  vector<vector<int>> xs(MAX), ys(MAX);
  for (int i = 0; i < N; ++i) {
    xs[X[i]].push_back(i);
    ys[Y[i]].push_back(i);
  }
  vector<int> xid(N), yid(N);
  for (int i = 0; i < MAX; ++i) {
    sort(xs[i].begin(), xs[i].end(), [&](int x, int y) {  
      return Y[x] < Y[y];
    });
    sort(ys[i].begin(), ys[i].end(), [&](int x, int y) {
      return X[x] < X[y];
    });
    for (int j = 0; j < int(xs[i].size()); ++j) {
      xid[xs[i][j]] = j;
    }
    for (int j = 0; j < int(ys[i].size()); ++j) {
      yid[ys[i][j]] = j;
    }
  }
  vector<bool> top(N), bot(N);
  vector<int> min_row(MAX, -1);
  vector<int> max_row(MAX, -1);
  vector<int> rem;
  auto Add = [&](int i, bool type) {
    if (type) {
      top[i] = true;
    } else {
      bot[i] = true;
    }
    int& mn = min_row[Y[i]];
    int& mx = max_row[Y[i]];
    if (mn == -1) {
      mn = i;
    }
    if (mx == -1) {
      mx = i;
    }
    if (X[mn] > X[i]) {
      if (mx != mn) rem.push_back(mn);
      mn = i;
    }
    if (X[mx] < X[i]) {
      if (mx != mn) rem.push_back(mx);
      mx = i;
    }
  };
  for (int i = 0; i < MAX; ++i) {
    if (xs[i].empty()) continue;
    Add(xs[i][0], false);
    Add(xs[i].back(), true);
  }
  debug(top, bot, rem);
  for (auto i : rem) {
    if (top[i] && bot[i]) {
      top[i] = bot[i] = false;
      continue;
    }
    if (top[i]) {
      top[i] = false;
      Add(xs[X[i]][xid[i] - 1], true);
    } else if (bot[i]) {
      bot[i] = false;
      Add(xs[X[i]][xid[i] + 1], false);
    }
  }
  for (int i = 0; i < N; ++i) {
    cout << (bot[i] || top[i]);
  }
  cout << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55128 KB Output is correct
2 Correct 19 ms 55228 KB Output is correct
3 Correct 18 ms 55064 KB Output is correct
4 Correct 19 ms 55120 KB Output is correct
5 Correct 19 ms 55132 KB Output is correct
6 Correct 19 ms 55132 KB Output is correct
7 Correct 19 ms 55128 KB Output is correct
8 Correct 19 ms 55132 KB Output is correct
9 Correct 18 ms 55132 KB Output is correct
10 Correct 19 ms 55132 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55128 KB Output is correct
2 Correct 19 ms 55228 KB Output is correct
3 Correct 18 ms 55064 KB Output is correct
4 Correct 19 ms 55120 KB Output is correct
5 Correct 19 ms 55132 KB Output is correct
6 Correct 19 ms 55132 KB Output is correct
7 Correct 19 ms 55128 KB Output is correct
8 Correct 19 ms 55132 KB Output is correct
9 Correct 18 ms 55132 KB Output is correct
10 Correct 19 ms 55132 KB Output is correct
11 Correct 19 ms 55132 KB Output is correct
12 Correct 19 ms 55132 KB Output is correct
13 Correct 20 ms 55132 KB Output is correct
14 Correct 18 ms 55132 KB Output is correct
15 Correct 19 ms 55128 KB Output is correct
16 Correct 18 ms 55140 KB Output is correct
17 Correct 19 ms 55140 KB Output is correct
18 Incorrect 18 ms 55132 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 58496 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 435 ms 119604 KB Output is correct
2 Correct 452 ms 119316 KB Output is correct
3 Correct 453 ms 118808 KB Output is correct
4 Correct 427 ms 118716 KB Output is correct
5 Correct 440 ms 118968 KB Output is correct
6 Correct 666 ms 128988 KB Output is correct
7 Correct 686 ms 129296 KB Output is correct
8 Correct 673 ms 129340 KB Output is correct
9 Correct 699 ms 129476 KB Output is correct
10 Correct 650 ms 129476 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55128 KB Output is correct
2 Correct 19 ms 55228 KB Output is correct
3 Correct 18 ms 55064 KB Output is correct
4 Correct 19 ms 55120 KB Output is correct
5 Correct 19 ms 55132 KB Output is correct
6 Correct 19 ms 55132 KB Output is correct
7 Correct 19 ms 55128 KB Output is correct
8 Correct 19 ms 55132 KB Output is correct
9 Correct 18 ms 55132 KB Output is correct
10 Correct 19 ms 55132 KB Output is correct
11 Correct 19 ms 55132 KB Output is correct
12 Correct 19 ms 55132 KB Output is correct
13 Correct 20 ms 55132 KB Output is correct
14 Correct 18 ms 55132 KB Output is correct
15 Correct 19 ms 55128 KB Output is correct
16 Correct 18 ms 55140 KB Output is correct
17 Correct 19 ms 55140 KB Output is correct
18 Incorrect 18 ms 55132 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55128 KB Output is correct
2 Correct 19 ms 55228 KB Output is correct
3 Correct 18 ms 55064 KB Output is correct
4 Correct 19 ms 55120 KB Output is correct
5 Correct 19 ms 55132 KB Output is correct
6 Correct 19 ms 55132 KB Output is correct
7 Correct 19 ms 55128 KB Output is correct
8 Correct 19 ms 55132 KB Output is correct
9 Correct 18 ms 55132 KB Output is correct
10 Correct 19 ms 55132 KB Output is correct
11 Correct 19 ms 55132 KB Output is correct
12 Correct 19 ms 55132 KB Output is correct
13 Correct 20 ms 55132 KB Output is correct
14 Correct 18 ms 55132 KB Output is correct
15 Correct 19 ms 55128 KB Output is correct
16 Correct 18 ms 55140 KB Output is correct
17 Correct 19 ms 55140 KB Output is correct
18 Incorrect 18 ms 55132 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55128 KB Output is correct
2 Correct 19 ms 55228 KB Output is correct
3 Correct 18 ms 55064 KB Output is correct
4 Correct 19 ms 55120 KB Output is correct
5 Correct 19 ms 55132 KB Output is correct
6 Correct 19 ms 55132 KB Output is correct
7 Correct 19 ms 55128 KB Output is correct
8 Correct 19 ms 55132 KB Output is correct
9 Correct 18 ms 55132 KB Output is correct
10 Correct 19 ms 55132 KB Output is correct
11 Correct 19 ms 55132 KB Output is correct
12 Correct 19 ms 55132 KB Output is correct
13 Correct 20 ms 55132 KB Output is correct
14 Correct 18 ms 55132 KB Output is correct
15 Correct 19 ms 55128 KB Output is correct
16 Correct 18 ms 55140 KB Output is correct
17 Correct 19 ms 55140 KB Output is correct
18 Incorrect 18 ms 55132 KB Output isn't correct
19 Halted 0 ms 0 KB -