Submission #1221924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221924		abczz	IOI Fever (JOI21_fever)	C++20	69 / 100	2057 ms	96036 KiB

fever

#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <map>
#define ll long long

using namespace std;

ll n, pardist[100000][8];
bool B[100000];
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
map <ll, ll> mp[4], R[4][100000];
array<ll, 2> P[100000];
array<ll, 3> par[100000][8];

void reindex(ll u) {
  int k = 0;
  for (auto [x, y] : mp[u]) {
    mp[u][x] = k++;
  }
}
void init() {
  for (int i=0; i<4; ++i) {
    mp[i].clear();
    for (int j=0; j<n; ++j) R[i][j].clear();
  }
  for (int i=0; i<n; ++i) for (int j=0; j<8; ++j) par[i][j] = {-1, -1, -1}, pardist[i][j] = (ll)1e18;
  for (int i=0; i<n; ++i) B[i] = 0, ++mp[0][P[i][0]];
  reindex(0);
  for (int i=0; i<n; ++i) R[0][mp[0][P[i][0]]][P[i][1]] = i;
  for (int i=0; i<n; ++i) ++mp[1][P[i][1]];
  reindex(1);
  for (int i=0; i<n; ++i) R[1][mp[1][P[i][1]]][P[i][0]] = i;
  for (int i=0; i<n; ++i) ++mp[2][P[i][0]+P[i][1]];
  reindex(2);
  for (int i=0; i<n; ++i) R[2][mp[2][P[i][0]+P[i][1]]][P[i][0]-P[i][1]] = i;
  for (int i=0; i<n; ++i) ++mp[3][P[i][0]-P[i][1]];
  reindex(3);
  for (int i=0; i<n; ++i) R[3][mp[3][P[i][0]-P[i][1]]][P[i][0]+P[i][1]] = i;
}
void down(ll x, ll y, ll t) {
  auto it = R[0][mp[0][x]].lower_bound(y-2*t+1);
  if (it == R[0][mp[0][x]].begin()) return;
  it = prev(it);
  pq.push({y-(y+P[it->second][1])/2, it->second, 0});
  if (pardist[it->second][4] > y-(y+P[it->second][1])/2) {
    pardist[it->second][4] = y-(y+P[it->second][1])/2, par[it->second][4] = {x, y, -1};
  }
}
void up(ll x, ll y, ll t) {
  auto it = R[0][mp[0][x]].lower_bound(y+2*t);
  if (it == R[0][mp[0][x]].end()) return;
  pq.push({(y+P[it->second][1]+1)/2-y, it->second, 2});
  if (pardist[it->second][0] > (y+P[it->second][1]+1)/2-y) {
    pardist[it->second][0] = (y+P[it->second][1]+1)/2-y, par[it->second][0] = {x, y, -1};
  }
}
void left(ll x, ll y, ll t) {
  auto it = R[1][mp[1][y]].lower_bound(x-2*t+1);
  if (it == R[1][mp[1][y]].begin()) return;
  it = prev(it);
  pq.push({x-(x+P[it->second][0])/2, it->second, 1});
  if (pardist[it->second][6] > x-(x+P[it->second][0])/2) {
    pardist[it->second][6] = x-(x+P[it->second][0])/2, par[it->second][6] = {x, y, -1};
  }
}
void right(ll x, ll y, ll t) {
  auto it = R[1][mp[1][y]].lower_bound(x+2*t);
  if (it == R[1][mp[1][y]].end()) return;
  pq.push({(x+P[it->second][0]+1)/2-x, it->second, 3});
  if (pardist[it->second][2] > (x+P[it->second][0]+1)/2-x) {
    pardist[it->second][2] = (x+P[it->second][0]+1)/2-x, par[it->second][2] = {x, y, -1};
  }
}
void upleft(ll x, ll y, ll t, ll dir) {
  auto it = R[2][mp[2][x+y]].lower_bound(x-y-2*t+1);
  if (it == R[2][mp[2][x+y]].begin()) return;
  it = prev(it);
  pq.push({x-P[it->second][0], it->second, dir});
  if (pardist[it->second][7] > x-P[it->second][0]) {
    pardist[it->second][7] = x-P[it->second][0], par[it->second][7] = {x, y, dir};
  }
}
void downright(ll x, ll y, ll t, ll dir) {
  auto it = R[2][mp[2][x+y]].lower_bound(x-y+2*t);
  if (it == R[2][mp[2][x+y]].end()) return;
  pq.push({P[it->second][0]-x, it->second, dir});
  if (pardist[it->second][3] > P[it->second][0]-x) {
    pardist[it->second][3] = P[it->second][0]-x, par[it->second][3] = {x, y, dir};
  }
}
void downleft(ll x, ll y, ll t, ll dir) {
  auto it = R[3][mp[3][x-y]].lower_bound(x+y-2*t);
  if (it == R[3][mp[3][x-y]].begin()) return;
  it = prev(it);
  pq.push({x-P[it->second][0], it->second, dir});
  if (pardist[it->second][5] > x-P[it->second][0]) {
    pardist[it->second][5] = x-P[it->second][0], par[it->second][5] = {x, y, dir};
  }
}
void upright(ll x, ll y, ll t, ll dir) {
  auto it = R[3][mp[3][x-y]].lower_bound(x+y+2*t);
  if (it == R[3][mp[3][x-y]].end()) return;
  pq.push({P[it->second][0]-x, it->second, dir});
  if (pardist[it->second][1] > P[it->second][0]-x) {
    pardist[it->second][1] = P[it->second][0]-x, par[it->second][1] = {x, y, dir};
  }
}
void solve(ll x, ll y, ll t, ll dir) {
  if (!dir) {
    up(x, y, t);
    upleft(x, y, t, 1);
    upright(x, y, t, 3);
  }
  else if (dir == 1) {
    right(x, y, t);
    upright(x, y, t, 2);
    downright(x, y, t, 0);
  }
  else if (dir == 2) {
    down(x, y, t);
    downleft(x, y, t, 1);
    downright(x, y, t, 3);
  }
  else {
    left(x, y, t);
    upleft(x, y, t, 2);
    downleft(x, y, t, 0);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<n; ++i) cin >> P[i][0] >> P[i][1];
  ll f = 0;
  for (int d=0; d<4; ++d) {
    init();
    pq.push({0, 0, d});
    ll tot = 0;
    while (!pq.empty()) {
      auto [w, u, dir] = pq.top();
      //cout << d << " " << w << " " << u << " " << dir << endl;
      pq.pop();
      if (B[u]) continue;
      ++tot;
      B[u] = 1;
      R[0][mp[0][P[u][0]]].erase(P[u][1]);
      R[1][mp[1][P[u][1]]].erase(P[u][0]);
      R[2][mp[2][P[u][0]+P[u][1]]].erase(P[u][0]-P[u][1]);
      R[3][mp[3][P[u][0]-P[u][1]]].erase(P[u][0]+P[u][1]);
      solve(P[u][0], P[u][1], w, dir);
      if (par[u][0][0] != -1) up(par[u][0][0], par[u][0][1], w);
      if (par[u][1][0] != -1) upright(par[u][1][0], par[u][1][1], w, par[u][1][2]);
      if (par[u][2][0] != -1) right(par[u][2][0], par[u][2][1], w);
      if (par[u][3][0] != -1) downright(par[u][3][0], par[u][3][1], w, par[u][3][2]);
      if (par[u][4][0] != -1) down(par[u][4][0], par[u][4][1], w);
      if (par[u][5][0] != -1) downleft(par[u][5][0], par[u][5][1], w, par[u][5][2]);
      if (par[u][6][0] != -1) left(par[u][6][0], par[u][6][1], w);
      if (par[u][7][0] != -1) upleft(par[u][7][0], par[u][7][1], w, par[u][7][2]);
    }
    f = max(f, tot);
  }
  cout << f << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 0 / 31