oj.uz

Submission #239366

# Submission time Handle Problem Language Result Execution time Memory
239366 2020-06-15T12:46:55 Z aggu_01000101 Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 551 ms 262148 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{
    node* left;
    node* right;
    char val;
};
node* version[(int)1e6 + 5];
int ptr[(int)1e6 + 5];
int ind = 1;
char build(int l, int u, int i, node* curr){
    if(l==u){
        return curr->val = 'a';
    }
    return curr->val = max(build(l, mid(l, u), lchild(i), curr->left = new node), build(mid(l, u)+1, u, rchild(i), curr->right = new node));
}
char query(int l, int u, int ll, node* curr){
    if(l>=ll && u<=ll) return curr->val;
    if(ll<=mid(l, u)){
        return query(l, mid(l, u), ll, curr->left);
    }
    return query(mid(l, u)+1, u, ll, curr->right);
}
node* update(int l, int u, node* curr, int ll, char v){
    node* temp = new node;
    if(l>=ll && u<=ll){
        temp -> val = v;
        return temp;
    }
    if(ll<=mid(l, u)){
         temp -> left = update(l, mid(l, u), curr->left, ll, v);
         temp -> right = curr -> right;
         return temp;
    }
    temp -> right = update(mid(l, u)+1, u, curr->right, ll, v);
    temp -> left = curr -> left;
    return temp;
}
void Init(){
    version[0] = new node;
    build(0, 1000000, 0, version[0]);
    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 88 ms 62968 KB Output is correct
2 Correct 86 ms 62972 KB Output is correct
3 Correct 85 ms 62968 KB Output is correct
4 Correct 83 ms 62968 KB Output is correct
5 Correct 90 ms 62968 KB Output is correct
6 Correct 85 ms 62968 KB Output is correct
7 Correct 85 ms 62968 KB Output is correct
8 Correct 85 ms 62968 KB Output is correct
9 Correct 83 ms 62968 KB Output is correct
10 Correct 90 ms 62968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 62912 KB Output is correct
2 Correct 83 ms 63096 KB Output is correct
3 Correct 93 ms 62968 KB Output is correct
4 Correct 83 ms 62968 KB Output is correct
5 Correct 86 ms 63096 KB Output is correct
6 Correct 89 ms 62956 KB Output is correct
7 Correct 93 ms 63096 KB Output is correct
8 Correct 84 ms 62968 KB Output is correct
9 Correct 87 ms 62968 KB Output is correct
10 Correct 85 ms 62968 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 63908 KB Output is correct
2 Correct 94 ms 63992 KB Output is correct
3 Correct 87 ms 64120 KB Output is correct
4 Correct 89 ms 64888 KB Output is correct
5 Correct 85 ms 64232 KB Output is correct
6 Correct 91 ms 65376 KB Output is correct
7 Correct 91 ms 65332 KB Output is correct
8 Correct 90 ms 64760 KB Output is correct
9 Correct 91 ms 64888 KB Output is correct
10 Correct 87 ms 63920 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -