Submission #379278

#	Time	Username	Problem	Language	Result	Execution time	Memory
379278		MilosMilutinovic	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	550 ms	142444 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int N=1000050,M=N*16;
int root[M],ls[M],rs[M],tsz,cnt,sz[N];
char ch[M];
void Set(int p,int&c,int ss,int se,int qi,char L){
    c=++tsz;ls[c]=ls[p];rs[c]=rs[p];ch[c]=L;
    if(ss==se)return;
	int mid=ss+se>>1;
    if(qi<=mid)Set(ls[p],ls[c],ss,mid,qi,L);
    else Set(rs[p],rs[c],mid+1,se,qi,L);
}
char Get(int c,int ss,int se,int qi){
    if(ss==se)return ch[c];
    int mid=ss+se>>1;
    if(qi<=mid)return Get(ls[c],ss,mid,qi);
    else return Get(rs[c],mid+1,se,qi);
}
void Init(){}
void TypeLetter(char L){
    cnt++;sz[cnt]=sz[cnt-1]+1;root[cnt]=root[cnt-1];
    Set(root[cnt],root[cnt],1,N,sz[cnt],L);
}
void UndoCommands(int x){
    cnt++;root[cnt]=root[cnt-x-1];
    sz[cnt]=sz[cnt-x-1];
}
char GetLetter(int x){
    return Get(root[cnt],1,N,x+1);
}

Compilation message (stderr)

scrivener.cpp: In function 'void Set(int, int&, int, int, int, char)':
scrivener.cpp:9:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |  int mid=ss+se>>1;
      |          ~~^~~
scrivener.cpp: In function 'char Get(int, int, int, int)':
scrivener.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int mid=ss+se>>1;
      |             ~~^~~

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