2716: [Violet 3]天使玩偶

Time Limit:?80 Sec??Memory Limit:?128 MB
Submit:?1473??Solved:?621
[Submit][Status][Discuss]

Description

Input

Output

Sample Input & Output

樣例過大，略

HINT

?

?

Source

Vani原創 歡迎移步 OJ2648

[Submit][Status][Discuss]

?

?

CDQ分治，分類討論拆絕對值的方式，分別查詢最優值。

?

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 inline int nextChar(void) { 6 const int siz = 1024; 7 static char buf[siz]; 8 static char *hd = buf + siz; 9 static char *tl = buf + siz; 10 if (hd == tl) 11 fread(hd = buf, 1, siz, stdin); 12 return int(*hd++); 13 } 14 15 inline int nextInt(void) { 16 register int ret = 0; 17 register int neg = false; 18 register int bit = nextChar(); 19 for (; bit < 48; bit = nextChar()) 20 if (bit == '-')neg ^= true; 21 for (; bit > 47; bit = nextChar()) 22 ret = ret * 10 + bit - 48; 23 return neg ? -ret : ret; 24 } 25 26 const int lim = 1000001; 27 const int siz = 1000005; 28 const int inf = 1000000007; 29 30 int n, m; 31 32 struct data { 33 int k, x, y, t, p; 34 inline friend bool operator < 35 (const data &a, const data &b) { 36 if (a.x != b.x) 37 return a.x < b.x; 38 else 39 return a.k < b.k; 40 } 41 }p[siz], s[siz], q[siz]; 42 43 int ans[siz]; 44 45 int now; 46 int bit[siz]; 47 int tim[siz]; 48 49 inline void add(int t, int k) { 50 for (; t < siz; t += t&-t) 51 if (bit[t] < k || tim[t] != now) 52 bit[t] = k, tim[t] = now; 53 } 54 55 inline int ask(int t) { 56 int ret = -inf; 57 for (; t; t -= t&-t) 58 if (ret < bit[t] && tim[t] == now) 59 ret = bit[t]; 60 return ret; 61 } 62 63 void cdqSolve(int l, int r) { 64 if (l >= r)return; 65 66 int mid = (l + r) >> 1; 67 68 cdqSolve(l, mid); 69 cdqSolve(mid + 1, r); 70 71 int t1 = l, t2 = mid + 1, tot = l; 72 73 while (t1 <= mid && t2 <= r) { 74 if (s[t1] < s[t2]) 75 q[tot++] = s[t1++]; 76 else 77 q[tot++] = s[t2++]; 78 } 79 80 while (t1 <= mid) 81 q[tot++] = s[t1++]; 82 83 while (t2 <= r) 84 q[tot++] = s[t2++]; 85 86 for (int i = l; i <= r; ++i) 87 s[i] = q[i]; 88 89 ++now; 90 91 for (int i = l; i <= r; ++i) 92 if (s[i].k && s[i].t > mid) { 93 int tmp = s[i].x + s[i].y - ask(s[i].y); 94 if (ans[s[i].p] > tmp) 95 ans[s[i].p] = tmp; 96 } 97 else if (!s[i].k && s[i].t <= mid) 98 add(s[i].y, s[i].x + s[i].y); 99 } 100 101 inline void cdqSolve1(void) { 102 memcpy(s, p, sizeof(s)); 103 cdqSolve(1, n + m); 104 } 105 106 inline void cdqSolve2(void) { 107 memcpy(s, p, sizeof(s)); 108 for (int i = 1; i <= n + m; ++i) 109 s[i].x = lim - s[i].x; 110 cdqSolve(1, n + m); 111 } 112 113 inline void cdqSolve3(void) { 114 memcpy(s, p, sizeof(s)); 115 for (int i = 1; i <= n + m; ++i) 116 s[i].y = lim - s[i].y; 117 cdqSolve(1, n + m); 118 } 119 120 inline void cdqSolve4(void) { 121 memcpy(s, p, sizeof(s)); 122 for (int i = 1; i <= n + m; ++i) 123 s[i].x = lim - s[i].x, 124 s[i].y = lim - s[i].y; 125 cdqSolve(1, n + m); 126 } 127 128 signed main(void) { 129 // freopen("in", "r", stdin); 130 // freopen("out", "w", stdout); 131 132 n = nextInt(); 133 m = nextInt(); 134 135 for (int i = 1; i <= n; ++i) { 136 p[i].x = nextInt(); 137 p[i].y = nextInt(); 138 p[i].k = 0; 139 p[i].t = i; 140 } 141 142 for (int i = 1; i <= m; ++i) { 143 p[i + n].k = nextInt() - 1; 144 p[i + n].x = nextInt(); 145 p[i + n].y = nextInt(); 146 p[i + n].t = i + n; 147 p[i + n].p = i; 148 } 149 150 for (int i = 1; i <= m; ++i) 151 ans[i] = inf; 152 153 cdqSolve1(); 154 cdqSolve2(); 155 cdqSolve3(); 156 cdqSolve4(); 157 158 for (int i = 1; i <= m; ++i) 159 if (p[i + n].k)printf("%d\n", ans[i]); 160 }

?

@Author: YouSiki

轉載于:https://www.cnblogs.com/yousiki/p/6245274.html

總結

以上是生活随笔為你收集整理的BZOJ 2716: [Violet 3]天使玩偶的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。