oj.uz

Submission #953690

# Submission time Handle Problem Language Result Execution time Memory
953690 2024-03-26T13:27:44 Z infrapolar Secret (JOI14_secret) C++17
0 / 100
 393 ms 4528 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 > center-block_size; 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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2800 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 111 ms 3056 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Incorrect 99 ms 2812 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 898965770.
4 Incorrect 368 ms 4528 KB Wrong Answer: Query(972, 988) - expected : 620937365, actual : 921366563.
5 Incorrect 391 ms 4440 KB Wrong Answer: Query(971, 985) - expected : 775804996, actual : 896270418.
6 Incorrect 370 ms 4352 KB Wrong Answer: Query(975, 984) - expected : 286812006, actual : 721748244.
7 Partially correct 382 ms 4340 KB Output isn't correct - number of calls to Secret by Init = 8008, maximum number of calls to Secret by Query = 1
8 Partially correct 377 ms 4348 KB Output isn't correct - number of calls to Secret by Init = 8008, maximum number of calls to Secret by Query = 1
9 Partially correct 379 ms 4436 KB Output isn't correct - number of calls to Secret by Init = 8008, maximum number of calls to Secret by Query = 1
10 Partially correct 393 ms 4312 KB Output isn't correct - number of calls to Secret by Init = 8008, maximum number of calls to Secret by Query = 1