Submission #1004909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004909		jonathanirvings	Tiles (BOI24_tiles)	C++17	100 / 100	199 ms	36176 KiB

Main

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

int max_line(int N, int, std::vector<int> X, std::vector<int> Y) {
  map<int, vector<pair<int, int>>> lines_at_x;
  for (int i = 0; i < N; ++i) {
    int j = (i + 1) % N;
    if (X[i] == X[j]) {
      if (X[i] > 0) {
        lines_at_x[X[i] - 1];
      }
      lines_at_x[X[i]].push_back(make_pair(min(Y[i], Y[j]), max(Y[i], Y[j])));
    }
  }
  int answer = 0;
  vector<int> parity_cnt(2);
  int odd_lines_cnt = 0;
  set<tuple<int, int, int>> current_lines;
  map<int, set<tuple<int, int, int>>::iterator> line_ends_at, line_starts_at;

  auto erase_current_line = [&] (set<tuple<int, int, int>>::iterator it) {
    --parity_cnt[get<2>(*it)];
    line_starts_at.erase(get<0>(*it));
    line_ends_at.erase(get<1>(*it));
    if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
      --odd_lines_cnt;
    }
    current_lines.erase(it);
  };

  auto insert_current_line = [&] (int start_line, int end_line, int parity) {
    if (line_ends_at.count(start_line)) {
      auto it = line_ends_at[start_line];
      if (get<2>(*it) == parity) {
        start_line = get<0>(*it);
        erase_current_line(it);
      }
    }
    if (line_starts_at.count(end_line)) {
      auto it = line_starts_at[end_line];
      if (get<2>(*it) == parity) {
        end_line = get<1>(*it);
        erase_current_line(it);
      }
    }

    auto it = current_lines.insert(
        make_tuple(start_line, end_line, parity)).first;
    ++parity_cnt[parity];
    line_starts_at[start_line] = it;
    line_ends_at[end_line] = it;
    if ((end_line - start_line) % 2 == 1) {
      ++odd_lines_cnt;
    }
  };

  for (auto [x, lines] : lines_at_x) {
    if (parity_cnt[1 - x % 2] == 0) {
      answer = x;
    }
    if (lines.size() == 0) {
      continue;
    }
    sort(lines.begin(), lines.end());
    int start_line = lines[0].first;
    for (int i = 0; i < static_cast<int>(lines.size()); ++i) {
      if (i + 1 == static_cast<int>(lines.size()) ||
          lines[i].second != lines[i + 1].first) {
        int end_line = lines[i].second;

        while (start_line < end_line) {
          auto it = current_lines.upper_bound(
              make_tuple(start_line, INT_MAX, INT_MAX));
          
          bool entering_polygon = false;
          if (it == current_lines.begin()) {
            entering_polygon = true;
          } else {
            --it;
            if (get<1>(*it) <= start_line) {
              entering_polygon = true;
            }
          }
          if (entering_polygon) {
            insert_current_line(start_line, end_line, x % 2);
            break;
          }
          
          int start_cur_line = get<0>(*it);
          int end_cur_line = get<1>(*it);
          int parity_cur_line = get<2>(*it);
          erase_current_line(it);

          if (x % 2 != parity_cur_line) {
            return answer;
          }
          
          if (start_cur_line < start_line) {
            insert_current_line(start_cur_line, start_line, x % 2);
          }
          if (end_line < end_cur_line) {
            insert_current_line(end_line, end_cur_line, x % 2);
          }
          start_line = end_cur_line;
        }

        if (i + 1 < static_cast<int>(lines.size())) {
          start_line = lines[i + 1].first;
        }
      }
    }
    if (odd_lines_cnt > 0) {
      return answer;
    }
  }
  return answer;
}

#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(N), Y(N);
  for (int i = 0; i < N; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  int result = max_line(N, M, X, Y);
  printf("%d\n", result);
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 22 / 22
• Subtask 6: 25 / 25
• Subtask 7: 10 / 10