| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 802302 | puppy | IOI Fever (JOI21_fever) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define int long long
#define all(v) (v).begin(), (v).end()
using namespace std;
struct Dot
{
int x, y;
};
int N;
Dot dot[100005];
int dir[100005];
int dis[100005][8];
const int inf = 1e18;
vector<pair<int, int>> line[4][100005][4];
vector<pair<int, int>> minor[100005][8];
int id[100005][4];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> dot[i].x >> dot[i].y;
if (i >= 2) {
dot[i].x -= dot[1].x;
dot[i].y -= dot[1].y;
}
}
dot[1] = {0, 0};
int ans = 0;
for (int k = 0; k < 4; k++) {
for (int i = 2; i <= N; i++) {
if (dot[i].y < dot[i].x && -dot[i].x < dot[i].y) {
dir[i] = 2;
}
else if (dot[i].y >= dot[i].x && dot[i].y > -dot[i].x) {
dir[i] = 3;
}
else if (dot[i].y < dot[i].x && dot[i].y <= -dot[i].x) {
dir[i] = 1;
}
else {
dir[i] = 0;
}
}
vector<int> cpx[4];
for (int i = 1; i <= N; i++) {
cpx[0].push_back(dot[i].y - dot[i].x);
cpx[1].push_back(dot[i].x + dot[i].y);
cpx[2].push_back(dot[i].y);
cpx[3].push_back(dot[i].x);
}
for (int k = 0; k < 4; k++) {
sort(all(cpx[k]));
cpx[k].erase(unique(all(cpx[k])), cpx[k].end());
}
auto lb = [&](int k, int i)
{
return lower_bound(all(cpx[k]), i) - cpx[k].begin();
};
for (int k = 0; k < 4; k++) {
for (int i = 0; i < (int)cpx[k].size(); i++) {
for (int j = 0; j < 4; j++) {
line[k][i][j].clear();
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 8; j++) {
minor[i][j].clear();
}
}
for (int i = 1; i <= N; i++) {
id[i][0] = lb(0, dot[i].y - dot[i].x);
id[i][1] = lb(1, dot[i].y + dot[i].x);
id[i][2] = lb(2, dot[i].y);
id[i][3] = lb(3, dot[i].x);
line[0][id[i][0]][dir[i]].push_back(make_pair(dot[i].x, i));
line[1][id[i][1]][dir[i]].push_back(make_pair(dot[i].x, i));
line[2][id[i][2]][dir[i]].push_back(make_pair(dot[i].x, i));
line[3][id[i][3]][dir[i]].push_back(make_pair(dot[i].y, i));
}
for (int k = 0; k < 4; k++) {
for (int i = 0; i < (int)cpx[k].size(); i++) {
for (int j = 0; j < 4; j++) {
sort(all(line[k][i][j]));
for (int l = 0; l < (int)line[k][i][j].size() - 1; l++) {
if (k < 2) {
minor[line[k][i][j][l].second][2*k].push_back(make_pair(2 * (line[k][i][j][l+1].first - line[k][i][j][l].first), line[k][i][j][l+1].second));
minor[line[k][i][j][l+1].second][2*k+1].push_back(make_pair(2 * (line[k][i][j][l+1].first - line[k][i][j][l].first), line[k][i][j][l].second));
}
else {
minor[line[k][i][j][l].second][2*k].push_back(make_pair(line[k][i][j][l+1].first - line[k][i][j][l].first, line[k][i][j][l+1].second));
minor[line[k][i][j][l+1].second][2*k+1].push_back(make_pair(line[k][i][j][l+1].first - line[k][i][j][l].first, line[k][i][j][l].second));
}
}
}
}
}
fill(&dis[0][0], &dis[100004][8], inf);
priority_queue<pair<int, pair<int, int>>> pq; pq.push(make_pair(0, make_pair(1, -1)));
while (!pq.empty()) {
int ver = pq.top().second.first, state = pq.top().second.second, now = -pq.top().first;
pq.pop();
if (state != -1) {
for (pair<int, int> p: minor[ver][state]) {
int nxt = p.second, newdis = now + p.first;
if (dis[nxt][state] > newdis) {
dis[nxt][state] = newdis;
pq.push(make_pair(-newdis, make_pair(nxt, state)));
}
}
}
if (dir[ver] == 0) {
auto it = lower_bound(all(line[0][id[ver][0]][3]), make_pair(dot[ver].x + (now + 1) / 2, -1));
if (it != line[0][id[ver][0]][3].end() && dis[(*it).second][0] > 2 * ((*it).first - dot[ver].x)) {
dis[(*it).second][0] = 2 * ((*it).first - dot[ver].x);
pq.push(make_pair(-dis[(*it).second][0], make_pair((*it).second, 0)));
}
auto it2 = lower_bound(all(line[1][id[ver][1]][1]), make_pair(dot[ver].x + (now + 1) / 2, -1));
if (it2 != line[1][id[ver][1]][1].end() && dis[(*it2).second][2] > 2 * ((*it2).first - dot[ver].x)) {
dis[(*it2).second][2] = 2 * ((*it2).first - dot[ver].x);
pq.push(make_pair(-dis[(*it2).second][2], make_pair((*it2).second, 2)));
}
auto it3 = lower_bound(all(line[2][id[ver][2]][2]), make_pair(dot[ver].x + now, -1));
if (it3 != line[2][id[ver][2]][2].end() && dis[(*it3).second][4] > (*it3).first - dot[ver].x) {
dis[(*it3).second][4] = (*it3).first - dot[ver].x;
pq.push(make_pair(-dis[(*it3).second][4], make_pair((*it3).second, 4)));
}
}
else if (dir[ver] == 1) {
auto it = lower_bound(all(line[0][id[ver][0]][2]), make_pair(dot[ver].x + (now + 1) / 2, -1));
if (it != line[0][id[ver][0]][2].end() && dis[(*it).second][0] > 2 * ((*it).first - dot[ver].x)) {
dis[(*it).second][0] = 2 * ((*it).first - dot[ver].x);
pq.push(make_pair(-dis[(*it).second][0], make_pair((*it).second, 0)));
}
auto it2 = lower_bound(all(line[1][id[ver][1]][0]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
if (it2 != line[1][id[ver][1]][0].begin()) {
--it2;
if (dis[(*it2).second][3] > 2 * (dot[ver].x - (*it2).first)) {
dis[(*it2).second][3] = 2 * (dot[ver].x - (*it2).first);
pq.push(make_pair(-dis[(*it2).second][3], make_pair((*it2).second, 3)));
}
}
auto it3 = lower_bound(all(line[3][id[ver][3]][3]), make_pair(dot[ver].y + now, -1));
if (it3 != line[3][id[ver][3]][3].end() && dis[(*it3).second][6] > (*it3).first - dot[ver].y) {
dis[(*it3).second][6] = (*it3).first - dot[ver].y;
pq.push(make_pair(-dis[(*it3).second][6], make_pair((*it3).second, 6)));
}
}
else if (dir[ver] == 2) {
auto it = lower_bound(all(line[0][id[ver][0]][1]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
if (it != line[0][id[ver][0]][1].begin()) {
--it;
if (dis[(*it).second][1] > 2 * (dot[ver].x - (*it).first)) {
dis[(*it).second][1] = 2 * (dot[ver].x - (*it).first);
pq.push(make_pair(-dis[(*it).second][1], make_pair((*it).second, 1)));
}
}
auto it2 = lower_bound(all(line[1][id[ver][1]][3]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
if (it2 != line[1][id[ver][1]][3].begin()) {
--it2;
if (dis[(*it2).second][3] > 2 * (dot[ver].x - (*it2).first)) {
dis[(*it2).second][3] = 2 * (dot[ver].x - (*it2).first);
pq.push(make_pair(-dis[(*it2).second][3], make_pair((*it2).second, 3)));
}
}
auto it3 = lower_bound(all(line[2][id[ver][2]][0]), make_pair(dot[ver].x - now + 1, -1));
if (it3 != line[2][id[ver][2]][0].begin()) {
--it3;
if (dis[(*it3).second][5] > dot[ver].x - (*it3).first) {
dis[(*it3).second][5] = dot[ver].x - (*it3).first;
pq.push(make_pair(-dis[(*it3).second][5], make_pair((*it3).second, 5)));
}
}
}
else {
auto it = lower_bound(all(line[0][id[ver][0]][0]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
if (it != line[0][id[ver][0]][0].begin()) {
--it;
if (dis[(*it).second][1] > 2 * (dot[ver].x - (*it).first)) {
dis[(*it).second][1] = 2 * (dot[ver].x - (*it).first);
pq.push(make_pair(-dis[(*it).second][1], make_pair((*it).second, 1)));
}
}
auto it2 = lower_bound(all(line[1][id[ver][1]][2]), make_pair(dot[ver].x + (now + 1) / 2, -1));
if (it2 != line[1][id[ver][1]][2].end() && dis[(*it2).second][2] > 2 * ((*it2).first - dot[ver].x)) {
dis[(*it2).second][2] = 2 * ((*it).first - dot[ver].x);
pq.push(make_pair(-dis[(*it2).second][2], make_pair((*it2).second, 2)));
}
auto it3 = lower_bound(all(line[3][id[ver][3]][1]), make_pair(dot[ver].x - now + 1, -1));
if (it3 != line[3][id[ver][3]][1].begin()) {
--it3;
if (dis[(*it3).second][7] > dot[ver].y - (*it3).first) {
dis[(*it3).second][7] = dot[ver].y - (*it3).first;
pq.push(make_pair(-dis[(*it3).second][7], make_pair((*it3).second, 7)));
}
}
}
}
int res = 1;
for (int i = 2; i <= N; i++) {
bool flag = false;
for (int j = 0; j < 8; j++) flag |= dis[i][j] != inf;
res += flag;
}
ans = max(ans, res);
for (int i = 2; i <= N; i++) {
int tmp = dot[i].y;
dot[i].y = dot[i].x;
dot[i].x = -tmp;
}
dir[1] = 0;
}
cout << ans << '\n';
}