oj.uz

Submission #953699

# Submission time Handle Problem Language Result Execution time Memory
953699 2024-03-26T13:37:17 Z infrapolar Secret (JOI14_secret) C++17
100 / 100
 399 ms 5624 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> memorizing;
int secret_layer(int x, int y){
    if (memorizing.find({x, y}) != memorizing.end())
        return memorizing[{x, y}];
    return memorizing[{x, y}] = Secret(x, y);
}
struct sparse_table
{
    vector<int> data[10];
    sparse_table(){}
    sparse_table(int sz, int* arr){
        data[0] = vector(arr, arr+sz);
        int block_size = 2;
        int j = 1;
        while (block_size < sz){
            data[j].assign(sz, 0);
            for (int begin = 0; begin < sz; begin+=2*block_size)
            {
                int center = min(sz-1, begin+block_size-1);
                data[j][center] = arr[center];
                for (int i = center - 1; i >= begin; i--)
                {
                    data[j][i] = secret_layer(arr[i], data[j][i+1]);
                }
                if (center != sz - 1)
                    data[j][center+1] = arr[center+1];
                for (int i = center+2; i < min(center+block_size+1, sz); i++)
                {
                    data[j][i] = secret_layer(data[j][i-1], arr[i]);
                }
                
            }
            block_size *= 2;
            j++;
        }
    }
    int query(int l, int r){
        if (l == r)
            return data[0][l];
        int layer = -1;
        int t = l ^ r;
        while (t){
            layer++;
            t >>= 1;
        }
        return secret_layer(data[layer][l], data[layer][r]);
    }
};
sparse_table str;
void Init(int N, int A[]) {
    str = sparse_table(N, A);
}

int Query(int L, int R) {
    return str.query(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 3408 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 108 ms 3568 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 107 ms 3468 KB Output is correct - number of calls to Secret by Init = 3842, maximum number of calls to Secret by Query = 1
4 Correct 384 ms 5588 KB Output is correct - number of calls to Secret by Init = 7487, maximum number of calls to Secret by Query = 1
5 Correct 368 ms 5624 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1
6 Correct 364 ms 5464 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1
7 Correct 373 ms 5596 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1
8 Correct 399 ms 5608 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1
9 Correct 376 ms 5544 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1
10 Correct 370 ms 5616 KB Output is correct - number of calls to Secret by Init = 7494, maximum number of calls to Secret by Query = 1