Submission #931428

#	Time	Username	Problem	Language	Result	Execution time	Memory
931428		AlphaMale06	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	2550 ms	262144 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

struct node{
    char c;
    int lc, rc;
};

vector<node> st;
vector<int> roots;
int nxtind[1000010];
int cntop=0;

void Build(int v, int l, int r){
    if(l>r)return;
    if(l==r){
        st.pb({0, -1, -1});
        return;
    }
    int mid=l+r>>1;
    st.pb({0, 2*v+1, 2*v+2});
    Build(2*v+1, l, mid);
    Build(2*v+2, mid+1, r);
}


void Add(int v, int l, int r, char c){
   if(l==r){
        st.pb({c, -1, -1});
        return;
   }
   int mid=l+r>>1;
   st.pb(st[v]);
   if(mid>=nxtind[cntop]){
        st[st.size()-1].lc=st.size();
        Add(st.size(), l, mid, c);
   }
   else{
        st[st.size()-1].rc=st.size();
        Add(st.size(), mid+1, r, c);
   }
}

char Get(int v, int l, int r, int ind){
    if(l==r)return st[v].c;
    int mid=l+r>>1;
    if(ind<=mid)return Get(st[v].lc, l, mid, ind);
    return Get(st[v].rc, mid+1, r, ind);
}

void TypeLetter(char c) {
    int nw=st.size();
    Add(roots.back(), 0, 1000010, c);
    roots.pb(nw);
    cntop++;
    nxtind[cntop]=nxtind[cntop-1]+1;
}

void UndoCommands(int num) {
    roots.pb(roots[roots.size()-num-1]);
    cntop++;
    nxtind[cntop]=nxtind[cntop-num-1];
}

char GetLetter(int ind) {
    return Get(roots.back(), 0, 1000010, ind);
}

void Init() {
   Build(0, 0, 1000010);
   roots.pb(0);
   nxtind[0]=0;
}

Compilation message (stderr)

scrivener.cpp: In function 'void Build(int, int, int)':
scrivener.cpp:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid=l+r>>1;
      |             ~^~
scrivener.cpp: In function 'void Add(int, int, int, char)':
scrivener.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |    int mid=l+r>>1;
      |            ~^~
scrivener.cpp: In function 'char Get(int, int, int, int)':
scrivener.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid=l+r>>1;
      |             ~^~

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