Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <fstream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <ctime>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef long long ll;
- #define all(v) v.begin(), v.end()
- #define TIME clock() * 1.0 / CLOCKS_PER_SEC
- #define TASK "castle"
- const int MAXN = (int)1e2 + 7;
- const int INF = (int)1e9 + 7;
- const ll LINF = (ll)1e18 + 7;
- const int MOD = (int)1e9 + 7;
- void file() {
- #ifdef Dron37_21
- freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #else
- freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout);
- #endif
- }
- inline int readChar();
- template <class T = int> inline T readInt();
- template <class T> inline void writeInt(T x, char end = 0);
- inline void writeChar(int x);
- inline void writeWord(const char *s);
- static const int buf_size = 4096;
- inline int getChar() {
- static char buf[buf_size];
- static int len = 0, pos = 0;
- if (pos == len)
- pos = 0, len = fread(buf, 1, buf_size, stdin);
- if (pos == len)
- return -1;
- return buf[pos++];
- }
- inline int readChar() {
- int c = getChar();
- while (c <= 32) {
- c = getChar();
- }
- return c;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getChar();
- return s == 1 ? x : -x;
- }
- inline pair<int, int> readPair() {
- int a = readInt(), b = readInt();
- return{ a, b };
- }
- static int write_pos = 0;
- static char write_buf[buf_size];
- inline void writeChar(int x) {
- if (write_pos == buf_size)
- fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
- write_buf[write_pos++] = x;
- }
- template <class T>
- inline void writeInt(T x, char end) {
- if (x < 0)
- writeChar('-'), x = -x;
- char s[24];
- int n = 0;
- while (x || !n)
- s[n++] = '0' + x % 10, x /= 10;
- while (n--)
- writeChar(s[n]);
- if (end)
- writeChar(end);
- }
- inline void writeWord(const char *s) {
- while (*s)
- writeChar(*s++);
- }
- struct Flusher {
- ~Flusher() {
- if (write_pos)
- fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
- }
- } flusher;
- /*const int MAX_MEM = (int)2e8;
- int mpos = 0;
- char mem[MAX_MEM];
- void * operator new (size_t n){
- char *res = mem + mpos;
- mpos += n;
- return (void *)res;
- }
- void operator delete (void * a) { }*/
- struct que {
- int type, val;
- que() {}
- que(int _type, int _val = -1) {
- type = _type, val = _val;
- }
- };
- bitset<MAXN> dp[MAXN][MAXN];
- int a[MAXN], sum, ind, P[MAXN];
- que Q[MAXN];
- void add(int val) {
- for (int t = 0; t <= sum; ++t) {
- dp[ind + 1][t] |= (dp[ind][t] << val);
- dp[ind + 1][t + val] |= dp[ind][t];
- dp[ind + 1][t] |= dp[ind][t];
- }
- sum += val;
- ++ind;
- }
- void del(int val) {
- for (int t = 0; t <= sum; ++t) {
- dp[ind][t] = 0;
- }
- sum -= val;
- --ind;
- }
- void dcp(int l, int r) {
- if (l == r) {
- if (Q[l].type == 3) {
- puts(!(sum % 3) && dp[ind][sum / 3][sum / 3] ? "YES" : "NO");
- }
- return;
- }
- int m = (l + r) / 2;
- for (int i = m + 1; i <= r; ++i) {
- if (Q[i].type == 2 && P[i] < l) {
- add(Q[i].val);
- }
- }
- dcp(l, m);
- for (int i = m + 1; i <= r; ++i) {
- if (Q[i].type == 2 && P[i] < l) {
- del(Q[i].val);
- }
- }
- for (int i = l; i <= m; ++i) {
- if (Q[i].type == 1 && P[i] > r) {
- add(Q[i].val);
- }
- }
- dcp(m + 1, r);
- for (int i = l; i <= m; ++i) {
- if (Q[i].type == 1 && P[i] > r) {
- del(Q[i].val);
- }
- }
- }
- int main() {
- file();
- dp[0][0][0] = 1;
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; ++i) {
- char c;
- scanf("\n%c", &c);
- if (c == '?') {
- Q[i] = que(3);
- continue;
- }
- int x;
- scanf("%d", &x);
- Q[i] = que(c - '0', x);
- }
- map<int, int> M;
- for (int i = 0; i < n; ++i) {
- if (Q[i].type == 1) {
- P[i] = INF;
- M[Q[i].val] = i;
- }
- if (Q[i].type == 2) {
- P[i] = M[Q[i].val];
- P[M[Q[i].val]] = i;
- }
- }
- dcp(0, n - 1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement