oj.uz

Submission #59240

# Submission time Handle Problem Language Result Execution time Memory
59240 2018-07-21T10:01:38 Z TadijaSebez Crayfish scrivener (IOI12_scrivener) C++11
100 / 100
 736 ms 197700 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1000050;
const int M=20*N;
int ls[M],rs[M],root[N],tsz;
char ch[M];
void Set(int p, int &c, int ss, int se, int qi, char s)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];ch[c]=s;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,s);
	else Set(rs[p],rs[c],mid+1,se,qi,s);
}
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(){}
int cnt=0,sz[N];
void TypeLetter(char s)
{
	cnt++;sz[cnt]=sz[cnt-1]+1;
	root[cnt]=root[cnt-1];
	Set(root[cnt],root[cnt],1,N,sz[cnt],s);
}
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 836 KB Output is correct
10 Correct 2 ms 836 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 904 KB Output is correct
5 Correct 2 ms 908 KB Output is correct
6 Correct 3 ms 912 KB Output is correct
7 Correct 2 ms 920 KB Output is correct
8 Correct 2 ms 920 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 2 ms 932 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1196 KB Output is correct
2 Correct 4 ms 1220 KB Output is correct
3 Correct 5 ms 1372 KB Output is correct
4 Correct 6 ms 1544 KB Output is correct
5 Correct 4 ms 1544 KB Output is correct
6 Correct 5 ms 1740 KB Output is correct
7 Correct 4 ms 1764 KB Output is correct
8 Correct 4 ms 1764 KB Output is correct
9 Correct 3 ms 1764 KB Output is correct
10 Correct 4 ms 1764 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 117544 KB Output is correct
2 Correct 372 ms 133316 KB Output is correct
3 Correct 414 ms 135516 KB Output is correct
4 Correct 430 ms 135516 KB Output is correct
5 Correct 476 ms 135516 KB Output is correct
6 Correct 401 ms 163500 KB Output is correct
7 Correct 471 ms 163500 KB Output is correct
8 Correct 426 ms 163500 KB Output is correct
9 Correct 532 ms 181460 KB Output is correct
10 Correct 320 ms 181460 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 181460 KB Output is correct
2 Correct 736 ms 181460 KB Output is correct
3 Correct 544 ms 181460 KB Output is correct
4 Correct 536 ms 181460 KB Output is correct
5 Correct 395 ms 181460 KB Output is correct
6 Correct 328 ms 181460 KB Output is correct
7 Correct 415 ms 185544 KB Output is correct
8 Correct 504 ms 185544 KB Output is correct
9 Correct 603 ms 185544 KB Output is correct
10 Correct 300 ms 197700 KB Output is correct