Advertisement
Guest User

Untitled

a guest
Jul 27th, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <cstring>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <set>
  14. #include <queue>
  15. #include <deque>
  16. #include <bitset>
  17. #include <cassert>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24.  
  25. #define all(v) v.begin(), v.end()
  26. #define TIME clock() * 1.0 / CLOCKS_PER_SEC
  27. #define TASK "castle"
  28.  
  29. const int MAXN = (int)1e2 + 7;
  30. const int INF = (int)1e9 + 7;
  31. const ll LINF = (ll)1e18 + 7;
  32. const int MOD = (int)1e9 + 7;
  33.  
  34. void file() {
  35. #ifdef Dron37_21
  36. freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  37. #else
  38. freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout);
  39. #endif
  40. }
  41.  
  42. inline int readChar();
  43. template <class T = int> inline T readInt();
  44. template <class T> inline void writeInt(T x, char end = 0);
  45. inline void writeChar(int x);
  46. inline void writeWord(const char *s);
  47.  
  48. static const int buf_size = 4096;
  49.  
  50. inline int getChar() {
  51. static char buf[buf_size];
  52. static int len = 0, pos = 0;
  53. if (pos == len)
  54. pos = 0, len = fread(buf, 1, buf_size, stdin);
  55. if (pos == len)
  56. return -1;
  57. return buf[pos++];
  58. }
  59.  
  60. inline int readChar() {
  61. int c = getChar();
  62. while (c <= 32) {
  63. c = getChar();
  64. }
  65. return c;
  66. }
  67.  
  68. template <class T>
  69. inline T readInt() {
  70. int s = 1, c = readChar();
  71. T x = 0;
  72. if (c == '-')
  73. s = -1, c = getChar();
  74. while ('0' <= c && c <= '9')
  75. x = x * 10 + c - '0', c = getChar();
  76. return s == 1 ? x : -x;
  77. }
  78.  
  79. inline pair<int, int> readPair() {
  80. int a = readInt(), b = readInt();
  81. return{ a, b };
  82. }
  83.  
  84. static int write_pos = 0;
  85. static char write_buf[buf_size];
  86.  
  87. inline void writeChar(int x) {
  88. if (write_pos == buf_size)
  89. fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  90. write_buf[write_pos++] = x;
  91. }
  92.  
  93. template <class T>
  94. inline void writeInt(T x, char end) {
  95. if (x < 0)
  96. writeChar('-'), x = -x;
  97.  
  98. char s[24];
  99. int n = 0;
  100. while (x || !n)
  101. s[n++] = '0' + x % 10, x /= 10;
  102. while (n--)
  103. writeChar(s[n]);
  104. if (end)
  105. writeChar(end);
  106. }
  107.  
  108. inline void writeWord(const char *s) {
  109. while (*s)
  110. writeChar(*s++);
  111. }
  112.  
  113. struct Flusher {
  114. ~Flusher() {
  115. if (write_pos)
  116. fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  117. }
  118. } flusher;
  119.  
  120. /*const int MAX_MEM = (int)2e8;
  121. int mpos = 0;
  122. char mem[MAX_MEM];
  123. void * operator new (size_t n){
  124. char *res = mem + mpos;
  125. mpos += n;
  126. return (void *)res;
  127. }
  128. void operator delete (void * a) { }*/
  129.  
  130. struct que {
  131. int type, val;
  132. que() {}
  133. que(int _type, int _val = -1) {
  134. type = _type, val = _val;
  135. }
  136. };
  137.  
  138. bitset<MAXN> dp[MAXN][MAXN];
  139. int a[MAXN], sum, ind, P[MAXN];
  140. que Q[MAXN];
  141.  
  142. void add(int val) {
  143. for (int t = 0; t <= sum; ++t) {
  144. dp[ind + 1][t] |= (dp[ind][t] << val);
  145. dp[ind + 1][t + val] |= dp[ind][t];
  146. dp[ind + 1][t] |= dp[ind][t];
  147. }
  148. sum += val;
  149. ++ind;
  150. }
  151.  
  152. void del(int val) {
  153. for (int t = 0; t <= sum; ++t) {
  154. dp[ind][t] = 0;
  155. }
  156. sum -= val;
  157. --ind;
  158. }
  159.  
  160. void dcp(int l, int r) {
  161. if (l == r) {
  162. if (Q[l].type == 3) {
  163. puts(!(sum % 3) && dp[ind][sum / 3][sum / 3] ? "YES" : "NO");
  164. }
  165. return;
  166. }
  167. int m = (l + r) / 2;
  168. for (int i = m + 1; i <= r; ++i) {
  169. if (Q[i].type == 2 && P[i] < l) {
  170. add(Q[i].val);
  171. }
  172. }
  173. dcp(l, m);
  174. for (int i = m + 1; i <= r; ++i) {
  175. if (Q[i].type == 2 && P[i] < l) {
  176. del(Q[i].val);
  177. }
  178. }
  179. for (int i = l; i <= m; ++i) {
  180. if (Q[i].type == 1 && P[i] > r) {
  181. add(Q[i].val);
  182. }
  183. }
  184. dcp(m + 1, r);
  185. for (int i = l; i <= m; ++i) {
  186. if (Q[i].type == 1 && P[i] > r) {
  187. del(Q[i].val);
  188. }
  189. }
  190. }
  191.  
  192. int main() {
  193. file();
  194. dp[0][0][0] = 1;
  195. int n;
  196. scanf("%d", &n);
  197. for (int i = 0; i < n; ++i) {
  198. char c;
  199. scanf("\n%c", &c);
  200. if (c == '?') {
  201. Q[i] = que(3);
  202. continue;
  203. }
  204. int x;
  205. scanf("%d", &x);
  206. Q[i] = que(c - '0', x);
  207. }
  208. map<int, int> M;
  209. for (int i = 0; i < n; ++i) {
  210. if (Q[i].type == 1) {
  211. P[i] = INF;
  212. M[Q[i].val] = i;
  213. }
  214. if (Q[i].type == 2) {
  215. P[i] = M[Q[i].val];
  216. P[M[Q[i].val]] = i;
  217. }
  218. }
  219. dcp(0, n - 1);
  220. return 0;
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement