Submission #821466

#	Time	Username	Problem	Language	Result	Execution time	Memory
821466		caganyanmaz	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	309 ms	127712 KiB

scrivener

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


constexpr static int MXSIZE = 3e7;
struct STree
{
        int left[MXSIZE], right[MXSIZE];
        int nxt = 1;
        STree()
        {
                left[0] = -1;
                right[0] = -1;
        }
        int set(int l, int r, int index, int i, int val)
        {
                if (r - l == 1)
                {
                        left[nxt] = val;
                        return nxt++;
                }
                int lindex = index != -1 ? left[index] : -1;
                int rindex = index != -1 ? right[index] : -1;
                int m = l+r>>1;
                if (i < m)
                        lindex = set(l, m, lindex, i, val);
                else
                        rindex = set(m, r, rindex, i, val);
                left[nxt] = lindex;
                right[nxt] = rindex;
                return nxt++;
        }
        int get(int l, int r, int index, int i)
        {
                assert(index != -1);
                if (r - l == 1)
                        return left[index];
                int m = l+r>>1;
                if (i < m)
                        return get(l, m, left[index], i);
                return get(m, r, right[index], i);
        }
};
constexpr static int MXN = 1e6;
constexpr static int MXS = MXN + 5;

int current = 0;
int root[MXS];
int _size[MXS];
STree st;





void Init() {}

void TypeLetter(char L)
{
        root[current+1] = st.set(0, MXS, root[current], _size[current], L);
        _size[current+1] = _size[current] + 1;
        current++;
}

void UndoCommands(int U)
{
        root[current+1] = root[current-U];
        _size[current+1] = _size[current-U];
        current++;
}

char GetLetter(int P)
{
        return st.get(0, MXS, root[current], P);

}

Compilation message (stderr)

scrivener.cpp: In member function 'int STree::set(int, int, int, int, int)':
scrivener.cpp:24:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |                 int m = l+r>>1;
      |                         ~^~
scrivener.cpp: In member function 'int STree::get(int, int, int, int)':
scrivener.cpp:38:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |                 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