Submission #757184

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

scrivener

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

const int N = 1e6 + 1;

struct node {
    char c;
    node *left, *right;
    node() : left(NULL), right(NULL) { };
    node(const char &x) : c(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, const char &x) {
        if (l == r) return new node(x);
        if (!v) v = new node;
        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));
    }
    char qry(node* &v, int l, int r, int u) {
        if (l == r) return v->c;
        int m = l + r >> 1;
        if (u <= m) return qry(v->left, l, m, u);
        return qry(v->right, m + 1, r, u);
    }
} st[N];

int cur[N];
int t;

void Init() {

}

void TypeLetter(char L) {
    st[t].root = st[t + 1].root = st[t].upd(st[t].root, 0, N - 1, cur[t]++, L);
    cur[t + 1] = cur[t];
    t++;
}

void UndoCommands(int U) {
    cur[t] = cur[t + 1] = cur[t - U - 1];
    st[t].root = st[t + 1].root = st[t - U - 1].root;
    t++;
}

char GetLetter(int P) {
    return st[t].qry(st[t].root, 0, N - 1, P);
}

Compilation message (stderr)

scrivener.cpp: In member function 'node* Persistent_Segment_Tree::upd(node*, int, int, int, const char&)':
scrivener.cpp:20:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int m = l + r >> 1;
      |                 ~~^~~
scrivener.cpp: In member function 'char Persistent_Segment_Tree::qry(node*&, int, int, int)':
scrivener.cpp:26:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         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