제출 #1037733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037733		MilosMilutinovic	Naval battle (CEOI24_battle)	C++14	100 / 100	2852 ms	702040 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int n, x[N], y[N];

char d[N];

set<pair<int, int>> mp[4 * N][4][4];

int val[N][4];

vector<int> xs[4];

bool del[N];
  
priority_queue<array<int, 3>> pq;

int Code(char c) {
  if (c == 'S') {
    return 0;
  }
  if (c == 'N') {
    return 1;
  }
  if (c == 'W') {
    return 2;
  }
  return 3;
}

void Add(int i) {
  if (d[i] == 'S') {
    {
      auto it = mp[val[i][2]][2][1].lower_bound({y[i], -1});
      if (it != mp[val[i][2]][2][1].end()) {
        int j = it->second;
        pq.push({-(y[j] - y[i]) / 2, i, j});
      }
    }
    {
      auto it = mp[val[i][1]][1][3].lower_bound({x[i], -1});
      if (it != mp[val[i][1]][1][3].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(x[i] - x[j]), i, j});
      }
    }
    {
      auto it = mp[val[i][0]][0][2].lower_bound({x[i], -1});
      if (it != mp[val[i][0]][0][2].end()) {
        int j = it->second;
        pq.push({-(x[j] - x[i]), i, j});
      }
    }
  }
  if (d[i] == 'N') {
    {
      auto it = mp[val[i][2]][2][0].lower_bound({y[i], -1});
      if (it != mp[val[i][2]][2][0].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(y[i] - y[j]) / 2, i, j});
      }
    }
    {
      auto it = mp[val[i][0]][0][3].lower_bound({x[i], -1});
      if (it != mp[val[i][0]][0][3].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(x[i] - x[j]), i, j});
      }
    }
    {
      auto it = mp[val[i][1]][1][2].lower_bound({x[i], -1});
      if (it != mp[val[i][1]][1][2].end()) {
        int j = it->second;
        pq.push({-(x[j] - x[i]), i, j});
      }
    }
  }
  if (d[i] == 'E') {
    {
      auto it = mp[val[i][3]][3][2].lower_bound({x[i], -1});
      if (it != mp[val[i][3]][3][2].end()) {
        int j = it->second;
        pq.push({-(x[j] - x[i]) / 2, i, j});
      }
    }
    {
      auto it = mp[val[i][1]][1][0].lower_bound({x[i], -1});
      if (it != mp[val[i][1]][1][0].end()) {
        int j = it->second;
        pq.push({-(x[j] - x[i]), i, j});
      }
    }
    {
      auto it = mp[val[i][0]][0][1].lower_bound({x[i], -1});
      if (it != mp[val[i][0]][0][1].end()) {
        int j = it->second;
        pq.push({-(x[j] - x[i]), i, j});
      }
    }
  }
  if (d[i] == 'W') {
    {
      auto it = mp[val[i][3]][3][3].lower_bound({x[i], -1});
      if (it != mp[val[i][3]][3][3].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(x[i] - x[j]) / 2, i, j});
      }
    }
    {
      auto it = mp[val[i][0]][0][0].lower_bound({x[i], -1});
      if (it != mp[val[i][0]][0][0].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(x[i] - x[j]), i, j});
      }
    }
    {
      auto it = mp[val[i][1]][1][1].lower_bound({x[i], -1});
      if (it != mp[val[i][1]][1][1].begin()) {
        it = prev(it);
        int j = it->second;
        pq.push({-(x[i] - x[j]), i, j});
      }
    }
  }
}

void Del(int i) {
  mp[val[i][0]][0][Code(d[i])].erase({x[i], i});
  mp[val[i][1]][1][Code(d[i])].erase({x[i], i});
  mp[val[i][2]][2][Code(d[i])].erase({y[i], i});
  mp[val[i][3]][3][Code(d[i])].erase({x[i], i});
  {
    auto it = mp[val[i][0]][0][Code(d[i])].lower_bound({x[i], -1});
    if (it != mp[val[i][0]][0][Code(d[i])].end()) {
      Add(it->second);
    }
    if (it != mp[val[i][0]][0][Code(d[i])].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[val[i][1]][1][Code(d[i])].lower_bound({x[i], -1});
    if (it != mp[val[i][1]][1][Code(d[i])].end()) {
      Add(it->second);
    }
    if (it != mp[val[i][1]][1][Code(d[i])].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[val[i][2]][2][Code(d[i])].lower_bound({y[i], -1});
    if (it != mp[val[i][2]][2][Code(d[i])].end()) {
      Add(it->second);
    }
    if (it != mp[val[i][2]][2][Code(d[i])].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[val[i][3]][3][Code(d[i])].lower_bound({x[i], -1});
    if (it != mp[val[i][3]][3][Code(d[i])].end()) {
      Add(it->second);
    }
    if (it != mp[val[i][3]][3][Code(d[i])].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> d[i];
  }
  for (int i = 0; i < n; i++) {
    xs[0].push_back(x[i] - y[i]);
    xs[1].push_back(x[i] + y[i]);
    xs[2].push_back(x[i]);
    xs[3].push_back(y[i]);
  }
  for (int i = 0; i < 4; i++) {
    sort(xs[i].begin(), xs[i].end());
    xs[i].erase(unique(xs[i].begin(), xs[i].end()), xs[i].end());
  }
  for (int i = 0; i < n; i++) {
    val[i][0] = (int) (lower_bound(xs[0].begin(), xs[0].end(), x[i] - y[i]) - xs[0].begin());
    val[i][1] = (int) (lower_bound(xs[1].begin(), xs[1].end(), x[i] + y[i]) - xs[1].begin());
    val[i][2] = (int) (lower_bound(xs[2].begin(), xs[2].end(), x[i]) - xs[2].begin());
    val[i][3] = (int) (lower_bound(xs[3].begin(), xs[3].end(), y[i]) - xs[3].begin());
  }
  for (int i = 0; i < n; i++) {
    mp[val[i][0]][0][Code(d[i])].emplace(x[i], i);
    mp[val[i][1]][1][Code(d[i])].emplace(x[i], i);
    mp[val[i][2]][2][Code(d[i])].emplace(y[i], i);
    mp[val[i][3]][3][Code(d[i])].emplace(x[i], i);
  }
  for (int i = 0; i < n; i++) {
    Add(i);
  }
  while (!pq.empty()) {
    int t = pq.top()[0];
    vector<int> ids;
    while (!pq.empty()) {
      if (pq.top()[0] != t) {
        break;
      }
      int i = pq.top()[1], j = pq.top()[2];
      pq.pop();
      if (!del[i] && !del[j]) {
        ids.push_back(i);
        ids.push_back(j);
      }
    }
    for (int i : ids) {
      if (!del[i]) {
        del[i] = true;
        Del(i);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (!del[i]) {
      cout << i + 1 << '\n';
    }
  }
  return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 24 / 24