oj.uz

Submission #821466

# Submission time Handle Problem Language Result Execution time Memory
821466 2023-08-11T10:34:08 Z caganyanmaz Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 309 ms 127712 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 324 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 944 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 104680 KB Output is correct
2 Correct 189 ms 115660 KB Output is correct
3 Correct 203 ms 114268 KB Output is correct
4 Correct 218 ms 93012 KB Output is correct
5 Correct 246 ms 99672 KB Output is correct
6 Correct 205 ms 125228 KB Output is correct
7 Correct 255 ms 64152 KB Output is correct
8 Correct 230 ms 94116 KB Output is correct
9 Correct 231 ms 127712 KB Output is correct
10 Correct 166 ms 94740 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 90292 KB Output is correct
2 Correct 287 ms 80464 KB Output is correct
3 Correct 225 ms 88804 KB Output is correct
4 Correct 243 ms 67916 KB Output is correct
5 Correct 199 ms 96188 KB Output is correct
6 Correct 196 ms 90788 KB Output is correct
7 Correct 205 ms 96588 KB Output is correct
8 Correct 274 ms 49100 KB Output is correct
9 Correct 309 ms 83312 KB Output is correct
10 Correct 149 ms 93900 KB Output is correct