首页 > 代码库 > BZOJ3476 [Usaco2014 Mar]The Lazy Cow
BZOJ3476 [Usaco2014 Mar]The Lazy Cow
这题做的我真是23333。。。
奥，这题表述不清，是说曼哈顿距离 <= k
首先我们坐标变换：
设(X, Y)为原坐标，则新坐标为(X + Y, X - Y + E)，为了防止y < 0
然后我们只要维护一堆边平行于坐标轴的正方形即可
方法是扫描线扫过去，然后用线段树维护y轴上的权值，也就是维护段+1和求全部的最大值操作。
然后发现Rank2。。。为了Rank1开始丧心病狂，写起了入读优化、、、
发现差4ms就Rank1，极为不爽。。。
于是czr大爷告诉我可以fread。。。一番折腾后。。。
Rank1！欧液！
1 /************************************************************** 2 Problem: 3476 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:2192 ms 7 Memory:64480 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cctype>12 #include <algorithm>13 14 #define lson p << 115 #define rson p << 1 | 116 #define Tag seg[p].tag17 using namespace std;18 const int N = 100005;19 const int E = 1000001;20 const int Height = (E << 1) - 1;21 const int M = (E << 3) + 10;22 23 struct point {24 int x, y, v;25 }a[N];26 inline bool operator < (const point &a, const point &b) {27 return a.x < b.x;28 }29 30 struct segment_tree {31 int tag, v;32 }seg[M];33 34 int n, k;35 int L, R, del;36 37 inline unsigned int read() {38 int x = 0;39 char ch = getchar();40 while (ch < ‘0‘ || ‘9‘ < ch)41 ch = getchar();42 while (‘0‘ <= ch && ch <= ‘9‘) {43 x = x * 10 + ch - ‘0‘;44 ch = getchar();45 }46 return x;47 }48 49 inline void refresh(int p, int v) {50 seg[p].v += v;51 seg[p].tag += v;52 }53 54 void insert(int p, int l, int r) {55 if (L <= l && r <= R) {56 refresh(p, del);57 return;58 }59 if (Tag) {60 refresh(lson ,Tag), refresh(rson, Tag);61 Tag = 0;62 }63 int mid = l + r >> 1;64 if (L <= mid)65 insert(lson, l, mid);66 if (mid < R) 67 insert(rson, mid + 1, r);68 seg[p].v = max(seg[lson].v, seg[rson].v);69 }70 71 int main() { 72 int i, j, X, Y, ans = 0;73 n = read(), k = read();74 k = k * 2 + 1;75 for (i = 1; i <= n; ++i) {76 a[i].v = read(), X = read(), Y = read();77 a[i].x = X + Y, a[i].y = X - Y + E;78 }79 sort(a + 1, a + n + 1);80 for (i = j = 1; i <= n; ++i) {81 while (a[i].x - a[j].x + 1 > k) {82 L = a[j].y - k + 1, R = a[j].y, del = -a[j].v;83 insert(1, 1, Height), ++j;84 }85 L = a[i].y - k + 1, R = a[i].y, del = a[i].v;86 insert(1, 1, Height);87 ans = max(ans, seg[1].v);88 }89 printf("%d\n", ans);90 return 0;91 }
↓下面这就是那个坑爹fread的版本。。。：
1 /************************************************************** 2 Problem: 3476 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1940 ms 7 Memory:66336 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cctype> 12 #include <algorithm> 13 14 #define lson p << 1 15 #define rson p << 1 | 1 16 #define Tag seg[p].tag 17 using namespace std; 18 const int N = 100005; 19 const int E = 1000001; 20 const int Height = (E << 1) - 1; 21 const int M = (E << 3) + 10; 22 const int MaxCH = 1900100; 23 struct point { 24 int x, y, v; 25 }a[N]; 26 inline bool operator < (const point &a, const point &b) { 27 return a.x < b.x; 28 } 29 30 struct segment_tree { 31 int tag, v; 32 }seg[M]; 33 34 int n, k; 35 int L, R, del; 36 char CH[MaxCH]; 37 int len, Left = 0; 38 39 inline unsigned int read() { 40 int x = 0; 41 char ch = getchar(); 42 while (ch < ‘0‘ || ‘9‘ < ch) 43 ch = getchar(); 44 while (‘0‘ <= ch && ch <= ‘9‘) { 45 x = x * 10 + ch - ‘0‘; 46 ch = getchar(); 47 } 48 return x; 49 } 50 51 inline int find() { 52 int x = 0; 53 while (CH[Left] < ‘0‘ || ‘9‘ < CH[Left]) 54 ++ Left; 55 while (‘0‘ <= CH[Left] && CH[Left] <= ‘9‘) 56 x = x * 10 + CH[Left++] - ‘0‘; 57 return x; 58 } 59 60 inline void refresh(int p, int v) { 61 seg[p].v += v; 62 seg[p].tag += v; 63 } 64 65 void insert(int p, int l, int r) { 66 if (L <= l && r <= R) { 67 refresh(p, del); 68 return; 69 } 70 if (Tag) { 71 refresh(lson, Tag), refresh(rson, Tag); 72 Tag = 0; 73 } 74 int mid = l + r >> 1; 75 if (L <= mid) 76 insert(lson, l, mid); 77 if (mid < R) 78 insert(rson, mid + 1, r); 79 seg[p].v = max(seg[lson].v, seg[rson].v); 80 } 81 82 int main() { 83 int i, j, X, Y, ans = 0; 84 len = fread(CH, 1, MaxCH, stdin); 85 CH[len] = ‘ ‘; 86 n = find(), k = find(); 87 k = k * 2 + 1; 88 for (i = 1; i <= n; ++i) { 89 a[i].v = find(), X = find(), Y = find(); 90 a[i].x = X + Y, a[i].y = X - Y + E; 91 } 92 sort(a + 1, a + n + 1); 93 for (i = j = 1; i <= n; ++i) { 94 while (a[i].x - a[j].x + 1 > k) { 95 L = a[j].y - k + 1, R = a[j].y, del = -a[j].v; 96 insert(1, 1, Height), ++j; 97 } 98 L = a[i].y - k + 1, R = a[i].y, del = a[i].v; 99 insert(1, 1, Height);100 ans = max(ans, seg[1].v);101 }102 printf("%d\n", ans);103 return 0;104 }
BZOJ3476 [Usaco2014 Mar]The Lazy Cow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。