Submission #3501949
Source Code Expand
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define pb push_back
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("E.in", "r", stdin);
freopen ("E.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3;
struct Node {
int x, y, id;
} lt[N];
struct Cmp {
inline bool operator () (const Node &lhs, const Node &rhs) {
return lhs.x != rhs.x ? lhs.x < rhs.x : lhs.y < rhs.y;
}
};
vector<int> G[N]; int con[N];
inline void Add(int u, int v) { G[u].pb(v); G[v].pb(u); }
int n, a, b, dis;
void Work(int d) {
sort(lt + 1, lt + n + 1, Cmp());
int l = 1, r = 0, pos = 1;
For (i, 1, n) {
while (l < n && (lt[l].x < lt[i].x - dis || (lt[l].x == lt[i].x - dis && lt[l].y < lt[i].y - d))) ++ l;
while (r < n && (lt[r + 1].x < lt[i].x - dis || (lt[r + 1].x == lt[i].x - dis && lt[r + 1].y <= lt[i].y + d))) ++ r;
con[lt[i].id] += r - l + 1;
for (chkmax(pos, l); pos <= r; ++ pos) Add(lt[i].id, lt[pos].id); -- pos;
}
}
long long ans = 0; bitset<N> vis;
void Dfs(int u) {
if (vis[u]) return ; vis[u] = true; ans += con[u];
for (int v : G[u]) Dfs(v);
}
int main() {
File();
n = read(), a = read(), b = read();
For (i, 1, n) {
int x = read(), y = read();
lt[i] = (Node) {x + y, x - y, i};
}
dis = max(abs(lt[a].x - lt[b].x), abs(lt[a].y - lt[b].y));
Work(dis); For (i, 1, n) swap(lt[i].x, lt[i].y); Work(dis - 1);
Dfs(a); printf ("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Manhattan Compass |
User |
zjp_shadow |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2202 Byte |
Status |
AC |
Exec Time |
74 ms |
Memory |
13440 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
2 ms |
2560 KB |
subtask0_1.txt |
AC |
2 ms |
2560 KB |
subtask0_2.txt |
AC |
2 ms |
2560 KB |
subtask1_0.txt |
AC |
42 ms |
7804 KB |
subtask1_1.txt |
AC |
37 ms |
7804 KB |
subtask1_10.txt |
AC |
54 ms |
9088 KB |
subtask1_11.txt |
AC |
37 ms |
7168 KB |
subtask1_12.txt |
AC |
29 ms |
4224 KB |
subtask1_13.txt |
AC |
29 ms |
4352 KB |
subtask1_14.txt |
AC |
50 ms |
8704 KB |
subtask1_15.txt |
AC |
37 ms |
7168 KB |
subtask1_16.txt |
AC |
39 ms |
8060 KB |
subtask1_17.txt |
AC |
40 ms |
8188 KB |
subtask1_18.txt |
AC |
74 ms |
13440 KB |
subtask1_19.txt |
AC |
37 ms |
7168 KB |
subtask1_2.txt |
AC |
52 ms |
9344 KB |
subtask1_20.txt |
AC |
42 ms |
8316 KB |
subtask1_21.txt |
AC |
40 ms |
8060 KB |
subtask1_22.txt |
AC |
71 ms |
13312 KB |
subtask1_23.txt |
AC |
59 ms |
11648 KB |
subtask1_24.txt |
AC |
39 ms |
7804 KB |
subtask1_3.txt |
AC |
49 ms |
8960 KB |
subtask1_4.txt |
AC |
43 ms |
8192 KB |
subtask1_5.txt |
AC |
40 ms |
8188 KB |
subtask1_6.txt |
AC |
73 ms |
13184 KB |
subtask1_7.txt |
AC |
59 ms |
10880 KB |
subtask1_8.txt |
AC |
29 ms |
4352 KB |
subtask1_9.txt |
AC |
40 ms |
8188 KB |