Submission #827183

#	Time	Username	Problem	Language	Result	Execution time	Memory
827183		Desh03	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	352 ms	137716 KiB

scrivener

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6;
int L[20 * N], R[20 * N], t;
char s[20 * N];

void upd(int &v, int l, int r, const int &x, const char &z) {
    ++t;
    L[t] = L[v];
    R[t] = R[v];
    v = t;
    if (l == r) {
        s[v] = z;
        return;
    }
    int m = l + r >> 1;
    if (x <= m) upd(L[v], l, m, x, z);
    else upd(R[v], m + 1, r, x, z);
    s[v] = s[L[v]] + s[R[v]];
}
 
char qry(int v, int l, int r, const int &x) {
    if (l == r) return s[v];
    int m = l + r >> 1;
    return x <= m ? qry(L[v], l, m, x) : qry(R[v], m + 1, r, x);
}
 
vector<pair<int, int>> st;

void Init() {
    st.push_back({0, 0});
}

void TypeLetter(char L) {
    st.push_back(st.back());
    upd(st.back().first, 0, N - 1, st.back().second++, L);
}

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

char GetLetter(int P) {
    return qry(st.back().first, 0, N - 1, P);
}

Compilation message (stderr)

scrivener.cpp: In function 'void upd(int&, int, int, const int&, const char&)':
scrivener.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int m = l + r >> 1;
      |             ~~^~~
scrivener.cpp: In function 'char qry(int, int, int, const int&)':
scrivener.cpp:26:15: 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: 26 / 26
• Subtask 5: 40 / 40