#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int Inf = 1'000'000'010;
int n;
int x[N], y[N];
int dir[N];
pii vec[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
set< pair<int, int> > st; // time, id
int mk[N];
int Collision(int a, int b){
if(x[a] > x[b]) swap(a, b);
if(x[a] == x[b]){
if(y[a] > y[b]) swap(a, b);
if(dir[a] == 3 && dir[b] == 1)
return abs(y[a] - y[b]) / 2;
return Inf;
}
if(y[a] == y[b]){
// if(y[a] > y[b]) swap(a, b);
if(dir[a] == 0 && dir[b] == 2)
return abs(x[a] - x[b]) / 2;
return Inf;
}
int dp_a = x[a] + y[a];
int dp_b = x[b] + y[b];
int dn_a = x[a] - y[a];
int dn_b = x[b] - y[b];
if(dp_a != dp_b && dn_a != dn_b)
return Inf;
int d = abs(x[a] - x[b]);
if(dp_a == dp_b){
if((dir[a] == 0 && dir[b] == 3) || (dir[a] == 1 && dir[b] == 2))
return d;
return Inf;
}
if((dir[a] == 0 && dir[b] == 1) || (dir[a] == 3 && dir[b] == 2))
return d;
return Inf;
}
int dis[N];
struct Line {
int spd = 1, sz;
vector<pii> Stop, Move;
vector<pii> ans, mn;
vector<int> lz;
void Apply(int id, int x){
ans[id] = min(ans[id], pii(mn[id].F + x, mn[id].S));
lz[id] = min(lz[id], x);
}
void Shift(int id){
if(lz[id] != 1)
Apply(id << 1, lz[id]), Apply(id << 1 | 1, lz[id]);
lz[id] = 1;
}
void Build(int id, int L, int R){
lz[id] = 1;
if(L + 1 == R){
ans[id] = {Inf, Stop[L].S};
mn[id] = Stop[L];
return ;
}
int mid = (L + R) >> 1;
Build(id << 1, L, mid);
Build(id<<1|1, mid, R);
ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Off(int id, int idx, int L, int R){
if(L + 1 == R){
mn[id].F = Inf + Inf;
return ;
}
int mid = (L + R) >> 1;
Shift(id);
if(idx < mid)
Off(id << 1, idx, L, mid);
else
Off(id<<1|1, idx, mid, R);
ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Add(int id, int l, int r, int x, int L, int R){
if(r <= L || R <= l) return ;
if(l <= L && R <= r){
Apply(id, x);
return ;
}
int mid = (L + R) >> 1;
Shift(id);
Add(id << 1, l, r, x, L, mid);
Add(id<<1|1, l, r, x, mid, R);
ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Add_Stop(int pos, int id){
Stop.pb({pos, id});
}
void Add_Move(int pos, int id){
Move.pb({pos, id});
}
void Init(){
sz = Stop.size();
if(Stop.empty())
return ;
for(auto &el : Stop)
el.F /= spd;
for(auto &el : Move)
el.F /= spd;
sort(all(Stop));
ans.resize(sz * 4);
mn.resize(sz * 4);
lz.resize(sz * 4);
Build(1, 0, sz);
}
void Infect_Move(int pos, int id, int tm){
int idx = lower_bound(all(Stop), pii(pos + tm, -1)) - Stop.begin();
if(idx == sz)
return ;
Add(1, idx, sz, -pos, 0, sz);
if(dis[ans[1].S] > ans[1].F){
dis[ans[1].S] = ans[1].F;
st.insert(ans[1]);
}
}
void Infect_Stop(int pos, int id, int tm){
int idx = lower_bound(all(Stop), pii(pos, id)) - Stop.begin();
assert(idx < sz);
Off(1, idx, 0, sz);
if(dis[ans[1].S] > ans[1].F){
dis[ans[1].S] = ans[1].F;
st.insert(ans[1]);
}
}
void Reset(){
Stop.clear();
Move.clear();
}
};
Line DIA[4][4][N], U[N], R[N];
int CP[N], CN[N], CXX[N], CYY[N];
int rv[4][4], ty[4][4];
void Infect(int u, int tm){
assert(mk[u] == 0);
mk[u] = 1;
int MAX = 1'000'000'000;
for(int d2 = 0; d2 < 4; d2 ++){
if((dir[u] + d2) % 2 == 0) continue;
int pos = rv[dir[u]][d2] ? MAX - x[u] : x[u];
DIA[dir[u]][d2][ ty[dir[u]][d2] ? CN[u] : CP[u]].Infect_Move(pos, u, tm);
pos = rv[d2][dir[u]] ? MAX - x[u] : x[u];
DIA[d2][dir[u]][ ty[d2][dir[u]] ? CN[u] : CP[u]].Infect_Stop(pos, u, tm);
}
}
int Solve(){
dir[0] = 0;
for(int i = 1; i < n; i++){
int X = abs(x[i] - x[0]);
int Y = abs(y[i] - y[0]);
if(X == Y){
if(x[i] < x[0]) dir[i] = 0;
else dir[i] = y[i] < y[0] ? 3 : 1;
} else {
if(X > Y){
if( x[i] < x[0]) dir[i] = 0;
else dir[i] = 2;
} else {
if( y[i] < y[0]) dir[i] = 3;
else dir[i] = 1;
}
}
}
// cerr << "!! " ;
// for(int i = 0; i < n; i++){
// cerr << dir[i] << ' ';
// }
// cerr << '\n';
// for(int i = 0; i < N; i++) R[i].Reset(), U[i].Reset();
for(int i = 0; i < 16; i++)
for(int j = 0; j < N; j++)
DIA[i >> 2][i & 3][j].Reset();
// for(int i = 0; i < N; i++) R[i].spd = U[i].spd = 2;
int MAX = 1'000'000'000;
for(int i = 0; i < n; i++){
for(int d2 = 0; d2 < 4; d2 ++){
if((dir[i] + d2) % 2 == 0) continue;
int pos = rv[dir[i]][d2] ? MAX - x[i] : x[i];
DIA[dir[i]][d2][ ty[dir[i]][d2] ? CN[i] : CP[i]].Add_Move(pos, i);
pos = rv[d2][dir[i]] ? MAX - x[i] : x[i];
DIA[d2][dir[i]][ ty[d2][dir[i]] ? CN[i] : CP[i]].Add_Stop(pos, i);
}
}
for(int i = 0; i < 16; i++)
for(int j = 0; j < N; j++)
DIA[i >> 2][i & 3][j].Init();
memset(mk, 0, sizeof mk);
fill(dis, dis + N, Inf);
dis[0] = 0;
st.insert({0, 0});
while(!st.empty()){
int fr = st.begin() -> S;
int tm = st.begin() -> F;
st.erase(st.begin());
// if(tm > Inf) continue;
Infect(fr, tm);
}
int res = 0;
for(int i = 0; i < n; i++)
res += mk[i];
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
rv[3][0] = 1; rv[1][0] = 1;
rv[2][1] = 1; rv[2][3] = 1;
ty[0][1] = ty[1][0] = ty[2][3] = ty[3][2] = 1;
cin >> n;
vector<int> cp, cn, cxx, cyy;
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
cp.pb(x[i] + y[i]);
cn.pb(x[i] - y[i]);
cxx.pb(x[i]);
cyy.pb(y[i]);
}
sort(all(cp));
sort(all(cn));
sort(all(cxx));
sort(all(cyy));
for(int i = 0; i < n; i++)
CP[i] = lower_bound(all(cp), x[i] + y[i]) - cp.begin();
for(int i = 0; i < n; i++)
CN[i] = lower_bound(all(cn), x[i] - y[i]) - cn.begin();
for(int i = 0; i < n; i++)
CXX[i] = lower_bound(all(cxx), x[i]) - cxx.begin();
for(int i = 0; i < n; i++)
CYY[i] = lower_bound(all(cyy), y[i]) - cyy.begin();
for(int i = 0; i < n; i++){
x[i] += x[i];
y[i] += y[i];
}
int ans = 0;
for(int _ = 0; _ < 4; _++){
ans = max(ans, Solve());
for(int i = 0; i < n; i++){
int _x = x[i];
x[i] = -y[i];
y[i] = _x;
}
// break;
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
226640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
226556 KB |
Output is correct |
| 2 |
Correct |
300 ms |
226600 KB |
Output is correct |
| 3 |
Correct |
317 ms |
226520 KB |
Output is correct |
| 4 |
Incorrect |
335 ms |
226560 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
