Submission #1037719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037719		MilosMilutinovic	Naval battle (CEOI24_battle)	C++14	76 / 100	3096 ms	701704 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][4][4 * N];

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

void Del(int i) {
  mp[0][Code(d[i])][val[i][0]].erase({x[i], i});
  mp[1][Code(d[i])][val[i][1]].erase({x[i], i});
  mp[2][Code(d[i])][val[i][2]].erase({y[i], i});
  mp[3][Code(d[i])][val[i][3]].erase({x[i], i});
  {
    auto it = mp[0][Code(d[i])][val[i][0]].lower_bound({x[i], -1});
    if (it != mp[0][Code(d[i])][val[i][0]].end()) {
      Add(it->second);
    }
    if (it != mp[0][Code(d[i])][val[i][0]].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[1][Code(d[i])][val[i][1]].lower_bound({x[i], -1});
    if (it != mp[1][Code(d[i])][val[i][1]].end()) {
      Add(it->second);
    }
    if (it != mp[1][Code(d[i])][val[i][1]].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[2][Code(d[i])][val[i][2]].lower_bound({y[i], -1});
    if (it != mp[2][Code(d[i])][val[i][2]].end()) {
      Add(it->second);
    }
    if (it != mp[2][Code(d[i])][val[i][2]].begin()) {
      it = prev(it);
      Add(it->second);
    }
  }
  {
    auto it = mp[3][Code(d[i])][val[i][3]].lower_bound({x[i], -1});
    if (it != mp[3][Code(d[i])][val[i][3]].end()) {
      Add(it->second);
    }
    if (it != mp[3][Code(d[i])][val[i][3]].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[0][Code(d[i])][val[i][0]].emplace(x[i], i);
    mp[1][Code(d[i])][val[i][1]].emplace(x[i], i);
    mp[2][Code(d[i])][val[i][2]].emplace(y[i], i);
    mp[3][Code(d[i])][val[i][3]].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: 0 / 24