Submission #757170

#	Time	Username	Problem	Language	Result	Execution time	Memory
757170		Desh03	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	524 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1;

struct node {
    int val;
    node *left, *right;
    node() : left(NULL), right(NULL) { };
    node(const int &x) : val(x), left(NULL), right(NULL) { };
    node(node* l, node* r) : left(l), right(r) { };
};

struct Persistent_Segment_Tree {
    node *root;
    Persistent_Segment_Tree() : root(NULL) { };
    node* upd(node* v, int l, int r, int u, int x) {
        if (l == r) return new node(x);
        int m = l + r >> 1;
        if (u <= m) return new node(upd(v->left, l, m, u, x), v->right);
        else return new node(v->left, upd(v->right, m + 1, r, u, x));
    }
    node* build(node *v, int l, int r) {
        if (l == r) return new node;
        int m = l + r >> 1;
        return new node(build(v->left, l, m), build(v->right, m + 1, r));
    }
    int qry(node* &v, int l, int r, int u) {
        if (l == r) return v->val;
        int m = l + r >> 1;
        if (u <= m) return qry(v->left, l, m, u);
        return qry(v->right, m + 1, r, u);
    }
    void build() {
        root = build(root, 0, N - 1);
    }
    void upd(int u, int x) {
        root = upd(root, 0, N - 1, u, x);
    }
    int qry(int u) {
        return qry(root, 0, N - 1, u);
    }
};

vector<Persistent_Segment_Tree> st;
int cur[N];

void Init() {
    st.push_back(Persistent_Segment_Tree());
    st[0].build();
}

void TypeLetter(char L) {
    st.back().upd(cur[st.size() - 1]++, L - 'a');
    cur[st.size()] = cur[st.size() - 1];
    st.push_back(st.back());
}

void UndoCommands(int U) {
    cur[st.size() - 1] = cur[st.size()] = cur[st.size() - U - 2];
    st.back() = st[st.size() - U - 2];
    st.push_back(st.back());
}

char GetLetter(int P) {
    return 'a' + st.back().qry(P);
}

Compilation message (stderr)

scrivener.cpp: In member function 'node* Persistent_Segment_Tree::upd(node*, int, int, int, int)':
scrivener.cpp:19:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int m = l + r >> 1;
      |                 ~~^~~
scrivener.cpp: In member function 'node* Persistent_Segment_Tree::build(node*, int, int)':
scrivener.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int m = l + r >> 1;
      |                 ~~^~~
scrivener.cpp: In member function 'int Persistent_Segment_Tree::qry(node*&, int, int, int)':
scrivener.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int m = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40