Submission #1123063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123063		cpptowin	Ruka (COI15_ruka)	C++20	0 / 100	2 ms	576 KiB

ruka

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 200010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define inf 50000010
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k) {
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k) {
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
struct TRIE {
    struct node {
        node *child[2];
        int cnt = 0;
        node() {
            for (int i = 0; i < 2; i++) child[i] = NULL;
        }
    };
    node *root;
    int cur = 0;
    TRIE() : cur(0) { root = new node(); };
    void clear() { root = new node(); }
    void add(int num) {
        node *p = root;
        for (int i = 28; i >= 0; i--) {
            int c = (num >> i) & 1;
            if (p->child[c] == NULL) {
                p->child[c] = new node();
            }
            p = p->child[c];
            p->cnt++;
        }
    }

    bool find(int x) {
        node *p = root;
        for (int i = 28; i >= 0; i--) {
            int c = (x >> i) & 1;
            if (p->child[c] == nullptr || p->child[c]->cnt == 0) {
                return false;
            }
            p = p->child[c];
        }
        return true;
    }

    bool remove(node *p, int x, int i) {
        if (i >= 0) {
            int c = (x >> i) & 1;
            if (remove(p->child[c], x, i - 1))
                p->child[c] = nullptr;
        }

        if (p != root) {
            p->cnt--;
            if (p->cnt == 0) {
                delete (p);
                return true;
            }
        }
        return false;
    }

    void remove(int x) {
        if (!find(x)) {
            return;
        }
        remove(root, x, 28);
    }

    int maxxor(int x) {
        node *p = root;
        int res = 0;
        for (int i = 28; i >= 0; i--) {
            int c = (x >> i) & 1;
            if (p->child[c ^ 1] != nullptr) {
                res += (1 << i);
                p = p->child[c ^ 1];
            } else
                p = p->child[c];
        }
        return res;
    }
    int getsmaller(int x) {
        int ans = 0;
        node *p = root;
        fod(i, 28, 0) {
            int t = bit(x, i);
            if (t == 1) {
                if (p->child[0] != NULL)
                    ans += p->child[0]->cnt;
                if (p->child[1] != NULL)
                    p = p->child[1];
                else
                    return ans;
            }
            if (t == 0) {
                if (p->child[0] != NULL)
                    p = p->child[0];
                else
                    return ans;
            }
        }
        return ans;
    }
} minn[4], maxx[4];
int n, q, ans;
array<int, 2> ff;
array<int, 2> a[maxn];
int f[maxn][2];
int now[2];
main() {
#define name "TASK"
    if (fopen(name ".inp", "r")) {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    f[0][0] = f[0][1] = 1;
    fo(i, 1, n) fo(j, 0, 1) {
        cin >> a[i][j];
        f[i][j] = f[i - 1][j] + a[i][j];
    }
    fod(i, n - 1, 1) fo(j, 0, 1) {
        minn[j].add(min(f[i][j], f[i + 1][j]) + inf);
        maxx[j].add(max(f[i][j], f[i + 1][j]) + inf);
    }
    fo(j, 0, 1) {
        minn[j + 2].add(min(f[0][j], f[1][j]) + inf);
        maxx[j + 2].add(max(f[0][j], f[1][j]) + inf);
    }
    int id = 1;
    int q;
    cin >> q;
    while (q--) {
        char t;
        cin >> t;
        if (t == 'B') {
            fo(j, 0, 1) {
                minn[j + 2].remove(min(f[id - 1][j], f[id][j] + now[j]) + inf);
                maxx[j + 2].remove(max(f[id - 1][j], f[id][j] + now[j]) + inf);
                f[id - 1][j] -= now[j];
                minn[j].add(min(f[id][j], f[id - 1][j]) + inf);
                maxx[j].add(max(f[id][j], f[id - 1][j]) + inf);
            }
            id--;
        } else if (t == 'F') {
            fo(j, 0, 1) {
                minn[j].remove(min(f[id][j], f[id + 1][j]) + inf);
                maxx[j].remove(max(f[id][j], f[id + 1][j]) + inf);
                f[id][j] += now[j];
                minn[j + 2].add(min(f[id][j], f[id + 1][j] + now[j]) + inf);
                maxx[j + 2].add(max(f[id][j], f[id + 1][j] + now[j]) + inf);
            }
            id++;
        } else if (t == 'C') {
            cin >> ff[0] >> ff[1];
            fo(j, 0, 1) {
                minn[j + 2].remove(min(f[id - 1][j], f[id][j] + now[j]) + inf);
                maxx[j + 2].remove(max(f[id - 1][j], f[id][j] + now[j]) + inf);
                now[j] += ff[j] - a[id][j];
                minn[j + 2].add(min(f[id - 1][j], f[id][j] + now[j]) + inf);
                maxx[j + 2].add(max(f[id - 1][j], f[id][j] + now[j]) + inf);
            }
            a[id] = ff;
        } else {
            ans = 0;
            fo(j, 0, 1) {
                ans += minn[j].getsmaller(-now[j] + inf) - maxx[j].getsmaller(-now[j] + inf);
                ans += minn[j + 2].getsmaller(inf) - maxx[j + 2].getsmaller(inf);
            }
            cout << ans;
            en;
        }
    }
}

Compilation message (stderr)

ruka.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main() {
      | ^~~~
ruka.cpp: In function 'int main()':
ruka.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 35
• Subtask 3: 0 / 56