| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 194323 | oscarsierra12 | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e6+2 ;
// int L[ 20*N ], R[ 20*N ], lazy [ 20*N ], sum [ 20*N ] ;
int lst[N], nec[N], q, last = 0, cur = 0;
char let[N] ;
int nodeG = 0;
int visit[N] ;
string ans ;
/*
struct info {
int l, r, nod ;
};
info fll ( int li, int ri, int node ) {
info x = {li,ri,node} ;
return x ;
}
int build ( info i ) {
if ( i.l == i.r )
return i.nod ;
info x = fll ( i.l, (i.l+i.r)/2, ++nodeG ) ;
L[i.nod] = build ( x ) ;
x = fll ( (i.l+i.r)/2+1, i.r, ++nodeG ) ;
R[i.nod] = build ( x ) ;
return i.nod ;
}
void propagate ( info i ) {
if ( lazy[i.nod] == -1 ) return ;
if ( L[i.nod] ) lazy[L[i.nod]] = lazy[i.nod] ;
if ( R[i.nod] ) lazy[R[i.nod]] = lazy[i.nod] ;
sum[i.nod] = lazy[i.nod]*(i.r-i.l+1) ;
lazy[i.nod] = -1 ;
}
void update ( info i, int a, int b, int val ) {
if ( a > b ) return ;
propagate ( i ) ;
int mid = (i.l+i.r)/2 ;
if ( i.l == a && i.r == b ) {
lazy[i.nod] = val ;
propagate ( i ) ;
return ;
}
info x = fll(i.l,mid,L[i.nod]) ;
info x2 = fll(mid+1, i.r, R[i.nod]) ;
if ( b <= mid ) update ( x, a, b, val ) ;
else if ( a > mid ) update ( x2, a, b, val ) ;
else {
update (x, a, mid, val) ;
update (x2, mid+1, b, val );
}
sum[i.nod] = sum[L[i.nod]] + sum[R[i.nod]] ;
}
int query ( info i, int a, int b ) {
if ( a > b ) return 0 ;
propagate(i) ;
if ( i.l == a && i.r == b ) return sum[i.nod] ;
int mid = (i.l+i.r)/2 ;
info x = fll(i.l,mid,L[i.nod]) ;
info x2 = fll(mid+1, i.r, R[i.nod]) ;
if ( b <= mid ) return query ( x, a, b ) ;
if ( a > mid ) return query ( x2, a, b ) ;
return query (x, a, mid) + query (x2, mid+1, b );
}
info fr ;*/
void Init() {
fr = fll(1,N-1,0) ;
// memset ( lazy, -1, sizeof lazy ) ;
// build ( fr ) ;
q = 0;
visit[0] = 1 ;
}
void TypeLetter(char L) {
++q ;
lst[q] = lst[q-1] ;
// update ( fr, q, q, 1 ) ;
let[q] = L ;
}
void UndoCommands(int U) {
++q ;
lst[q] = q ;
nec[q] = U ;
last = q ;
}
char GetLetter(int P) {
if ( last == 0 )
for ( int i = q; i ; --i ) ans.push_back (let[i]) ;
while ( !visit[last] ) {
int pos = lst[last] - nec[last] - 1 ;
for ( int i = pos ; i > lst[pos] ; --i ) ans.push_back(let[i]);
visit[last] = 1 ;
last = lst [ pos ] ;
}
if ( !cur ) reverse(ans.begin(), ans.end()), cur= 1 ;
// int lw = 1, hg = q ;
// P++ ;
// while ( lw < hg ) {
// int mid = (lw+hg+1) / 2 ;
// int letters = query ( fr, 1, mid ) ;
// if ( letters < P ) lw = mid ;
// else if ( letters > P ) hg = mid-1 ;
// else {
// if ( query(fr, mid,mid) ) lw = mid ;
// else hg = mid-1 ;
// }
// }
return ans[P] ;
}