oj.uz

Submission #953696

# Submission time Handle Problem Language Result Execution time Memory
953696 2024-03-26T13:33:48 Z infrapolar Secret (JOI14_secret) C++17
100 / 100
 383 ms 4500 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
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(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(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(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 105 ms 2728 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 106 ms 2736 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 105 ms 2736 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 377 ms 4260 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 373 ms 4436 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 378 ms 4220 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 372 ms 4436 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 379 ms 4500 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 378 ms 4260 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 383 ms 4256 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1