oj.uz

Submission #197032

# Submission time Handle Problem Language Result Execution time Memory
197032 2020-01-18T08:00:15 Z dennisstar Crayfish scrivener (IOI12_scrivener) C++11
100 / 100
 640 ms 186076 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
#define fastio ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

struct node {
	char ch; int l, r;
}nd[31000010]; int nd_tp;
int root[1000010];
int sz[1000010], tp;

int new_node() { nd[nd_tp]={0,-1,-1}; return nd_tp++; }

inline void upd(int now, int i, int t, int s, int e, char val) {
	assert(now!=-1);
	if (s==e) { nd[now].ch=val; return ; }
	int md=(s+e)/2;
	if (t<=md) {
		nd[now].l=new_node();
		nd[now].r=(i!=-1?nd[i].r:-1);
		upd(nd[now].l, i!=-1?nd[i].l:-1, t, s, md, val);
	}
	else {
		nd[now].l=(i!=-1?nd[i].l:-1);
		nd[now].r=new_node();
		upd(nd[now].r, i!=-1?nd[i].r:-1, t, md+1, e, val);
	}
}
inline char get(int now, int t, int s, int e) {
	if (s==e) return nd[now].ch;
	int md=(s+e)/2;
	if (t<=md) return get(nd[now].l, t, s, md);
	else return get(nd[now].r, t, md+1, e);
} 

void Init() { root[0]=new_node(); tp=1; memset(sz, 0, sizeof(sz)); }

void TypeLetter(char L) {
	root[tp]=new_node();
	sz[tp]=sz[tp-1]+1;
	upd(root[tp], root[tp-1], sz[tp], 1, 1000000, L);
	tp++;
}

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

char GetLetter(int P) { return get(root[tp-1], P+1, 1, 1000000); }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4088 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Correct 5 ms 4216 KB Output is correct
7 Correct 5 ms 4216 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4216 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4220 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4244 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct
8 Correct 7 ms 4216 KB Output is correct
9 Correct 6 ms 4216 KB Output is correct
10 Correct 5 ms 4216 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4600 KB Output is correct
2 Correct 7 ms 4600 KB Output is correct
3 Correct 7 ms 4732 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 4600 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 4984 KB Output is correct
9 Correct 7 ms 4984 KB Output is correct
10 Correct 7 ms 4600 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 153324 KB Output is correct
2 Correct 380 ms 168440 KB Output is correct
3 Correct 437 ms 165752 KB Output is correct
4 Correct 454 ms 133476 KB Output is correct
5 Correct 429 ms 144520 KB Output is correct
6 Correct 388 ms 182236 KB Output is correct
7 Correct 414 ms 90568 KB Output is correct
8 Correct 404 ms 135360 KB Output is correct
9 Correct 437 ms 186076 KB Output is correct
10 Correct 290 ms 136344 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 131916 KB Output is correct
2 Correct 501 ms 117332 KB Output is correct
3 Correct 441 ms 128392 KB Output is correct
4 Correct 453 ms 97484 KB Output is correct
5 Correct 359 ms 139216 KB Output is correct
6 Correct 354 ms 131080 KB Output is correct
7 Correct 367 ms 139624 KB Output is correct
8 Correct 567 ms 68628 KB Output is correct
9 Correct 640 ms 120288 KB Output is correct
10 Correct 289 ms 135292 KB Output is correct