oj.uz

Submission #239436

# Submission time Handle Problem Language Result Execution time Memory
239436 2020-06-15T14:52:36 Z aggu_01000101 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 527 ms 185720 KB 
#include <bits/stdc++.h>
//#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
struct node{
    int l;
    int r;
    char val;
};
node buffer[100*(1000000)];
int cnode = 0;
int initnode(int left = -1, int right = -1, char v = 'A'){
    buffer[cnode].l = left;
    buffer[cnode].r = right;
    buffer[cnode].val = v;
    return cnode++;
}
signed version[(int)1e6 + 5];
signed ptr[(int)1e6 + 5];
signed ind = 1;
char query(int l, int u, int ll, int i){
    if(l>=ll && u<=ll) return buffer[i].val;
    if(ll<=mid(l, u)){
        return query(l, mid(l, u), ll, buffer[i].l);
    }
    return query(mid(l, u)+1, u, ll, buffer[i].r);
}
int update(int l, int u, int i, int ll, char v){
    //cout<<"update "<<l<<" "<<u<<" "<<ll<<" "<<v<<"\n";
    if(l>=ll && u<=ll) return initnode(-1, -1, v);
    int tr = initnode();
    if(i!=-1) buffer[tr].l = buffer[i].l;
    if(i!=-1) buffer[tr].r = buffer[i].r;
    if(ll<=mid(l, u)){
        buffer[tr].l = update(l, mid(l, u), buffer[tr].l, ll, v);
    }
    else buffer[tr].r = update(mid(l, u)+1, u, buffer[tr].r, ll, v);
    return tr;
}
void Init(){
    version[0] = initnode();
    ptr[0] = 0;
}
void TypeLetter(char l){
    version[ind] = update(0, 1000000, version[ind - 1], ptr[ind-1], l);
    ptr[ind] = ptr[ind-1] + 1;
    ind++;
}
void UndoCommands(signed u){
    version[ind] = version[ind-1-u];
    ptr[ind] = ptr[ind - 1 - u];
    ind++;
}
char GetLetter(signed p){
    return query(0, 1000000, p, version[ind - 1]);
}
/*signed main(){
    Init();
    int q;
    cin>>q;
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            char l;
            cin>>l;
            TypeLetter(l);
        }
        else if(type==2){
            int u;
            cin>>u;
            UndoCommands(u);
        }
        else{
            int pos;
            cin>>pos;
            cout<<GetLetter(pos)<<endl;
        }
    }
}*/
/*
 1 a
 1 b
 3 1
 1 d
 2 2
 2 1
 3 2
 1 e
 2 1
 2 5
 1 c
 3 2
 2 2
 3 2
 */

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 6 ms 768 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 152120 KB Output is correct
2 Correct 365 ms 167928 KB Output is correct
3 Correct 392 ms 165240 KB Output is correct
4 Correct 442 ms 133076 KB Output is correct
5 Correct 443 ms 143864 KB Output is correct
6 Correct 402 ms 181856 KB Output is correct
7 Correct 451 ms 89848 KB Output is correct
8 Correct 419 ms 134904 KB Output is correct
9 Correct 427 ms 185720 KB Output is correct
10 Correct 332 ms 136240 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 130424 KB Output is correct
2 Correct 527 ms 115572 KB Output is correct
3 Correct 472 ms 127224 KB Output is correct
4 Correct 442 ms 95992 KB Output is correct
5 Correct 370 ms 138616 KB Output is correct
6 Correct 384 ms 130552 KB Output is correct
7 Correct 443 ms 139000 KB Output is correct
8 Correct 491 ms 67652 KB Output is correct
9 Correct 506 ms 119276 KB Output is correct
10 Correct 333 ms 135032 KB Output is correct