oj.uz

답안 #567458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567458 2022-05-23T13:55:36 Z shahriarkhan 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 510 ms 246968 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e6 + 5 ;

int od = 0 ;

string s = "" ;

struct Node
{
    int left = 0 , right = 0 , sum = 0 ;
} emp ;

struct psegtree
{
    int cur = 0 , cnt = 0 , N ;

    vector<Node> T ;

    vector<int> root ;

    void init(int n , int m)
    {
        N = n ;
        T = vector<Node> (20*n + 5 , emp) ;
        root = vector<int> (m + 5 , 0) ;
    }

    int _update(int node , int low , int high , int idx , int val)
    {
        if((idx<low) || (idx>high)) return 0 ;
        if((low==high) && (low==idx))
        {
            ++cur ;
            T[cur].sum = T[node].sum + val ;
            return cur ;
        }
        int mid = (low+high)>>1 , left = T[node].left , right = T[node].right , par = ++cur ;
        if(idx<=mid) T[par].left = _update(left,low,mid,idx,val) , T[par].right = right ;
        else T[par].left = left , T[par].right = _update(right,mid+1,high,idx,val) ;
        T[par].sum = T[T[par].left].sum + T[T[par].right].sum ;
        return par ;
    }

    void add(int idx)
    {
        ++cnt ;
        root[cnt] = _update(root[cnt-1],1,N,idx,1) ;
    }

    void undo(int x)
    {
        ++cnt ;
        root[cnt] = root[cnt-x-1] ;
    }

    int _query(int node , int low , int high , int idx)
    {
        if(low==high) return low ;
        int mid = (low+high)>>1 , left = T[node].left , right = T[node].right ;
        if(T[left].sum>=idx) return _query(left,low,mid,idx) ;
        else return _query(right,mid+1,high,idx-T[left].sum) ;
    }

    int get_val(int idx)
    {
        return _query(root[cnt],1,N,idx) ;
    }
} P ;

void Init()
{
    P.init(MX,MX) ;
}

void TypeLetter(char L)
{
    s += L ;
    P.add(++od) ;
}

void UndoCommands(int U)
{
    P.undo(U) ;
}

char GetLetter(int p)
{
    return s[P.get_val(p+1)-1] ;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 239004 KB Output is correct
2 Correct 101 ms 238996 KB Output is correct
3 Correct 98 ms 239012 KB Output is correct
4 Correct 99 ms 239032 KB Output is correct
5 Correct 108 ms 239044 KB Output is correct
6 Correct 95 ms 238932 KB Output is correct
7 Correct 98 ms 239052 KB Output is correct
8 Correct 97 ms 239044 KB Output is correct
9 Correct 101 ms 238936 KB Output is correct
10 Correct 111 ms 239004 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 238960 KB Output is correct
2 Correct 102 ms 238928 KB Output is correct
3 Correct 103 ms 239052 KB Output is correct
4 Correct 105 ms 238980 KB Output is correct
5 Correct 98 ms 238988 KB Output is correct
6 Correct 99 ms 239052 KB Output is correct
7 Correct 101 ms 239000 KB Output is correct
8 Correct 106 ms 239032 KB Output is correct
9 Correct 98 ms 239052 KB Output is correct
10 Correct 104 ms 239076 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 238972 KB Output is correct
2 Correct 106 ms 239008 KB Output is correct
3 Correct 99 ms 239156 KB Output is correct
4 Correct 96 ms 239096 KB Output is correct
5 Correct 103 ms 239140 KB Output is correct
6 Correct 105 ms 239004 KB Output is correct
7 Correct 105 ms 238992 KB Output is correct
8 Correct 99 ms 239036 KB Output is correct
9 Correct 99 ms 239032 KB Output is correct
10 Correct 101 ms 238972 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 243640 KB Output is correct
2 Correct 360 ms 243972 KB Output is correct
3 Correct 354 ms 244648 KB Output is correct
4 Correct 380 ms 246008 KB Output is correct
5 Correct 482 ms 244892 KB Output is correct
6 Correct 372 ms 244092 KB Output is correct
7 Correct 448 ms 245812 KB Output is correct
8 Correct 404 ms 245156 KB Output is correct
9 Correct 423 ms 244448 KB Output is correct
10 Correct 314 ms 244328 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 244636 KB Output is correct
2 Correct 510 ms 245724 KB Output is correct
3 Correct 501 ms 245336 KB Output is correct
4 Correct 438 ms 246968 KB Output is correct
5 Correct 374 ms 244752 KB Output is correct
6 Correct 359 ms 244352 KB Output is correct
7 Correct 377 ms 244716 KB Output is correct
8 Correct 438 ms 245916 KB Output is correct
9 Correct 489 ms 245828 KB Output is correct
10 Correct 325 ms 244060 KB Output is correct