oj.uz

Submission #349934

# Submission time Handle Problem Language Result Execution time Memory
349934 2021-01-18T17:59:03 Z blue Secret (JOI14_secret) C++17
0 / 100
 1000 ms 8556 KB 
#include "secret.h"
#include <iostream>
#include <vector>
using namespace std;


/**/

/**/




//midpoint, endpoin
int res[1000][1000];

int N;
vector<int> A(1000);

void precompute(int a, int b)
{
    if(a == b)
    {
        res[a][a] = A[a];
        return;
    }
    if(a+1 == b)
    {
        res[a][b] = A[b];
        res[a][a] = A[a];
        return;
    }

    int m = (a+b)/2;

    res[m][m+1] = A[m+1];
    for(int i = m+2; i <= N-1; i++) res[m][i] = Secret(res[m][i-1], A[i]);

    res[m][m] = A[m];
    for(int i = m-1; i >= 0; i--) res[m][i] = Secret(res[m][i+1], A[i]);

    precompute(a, m);
    precompute(m+1, b);
}

void Init(int n, int a[])
{
    N = n;
    for(int i = 0; i < N; i++) A[i] = a[i];

    precompute(0, N-1);
}

int query1(int L, int R, int a, int b)
{
    int m = (a+b)/2;
    if(L <= m && m+1 <= R) return Secret(res[m][L], res[m][R]);
    else if(R <= m) return query1(L, R, a, m);
    else return query1(L, R, m+1, b);
}

int Query(int L, int R)
{
    if(L == R) return A[L];
    if(L+1 == R) return Secret(A[L], A[R]);
    return query1(L, R, 0, N-1);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 256 ms 4460 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 268 ms 4544 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 259 ms 4460 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 993 ms 8556 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 985 ms 8336 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 984 ms 8312 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 154975445.
7 Incorrect 986 ms 8300 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 996 ms 8300 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 1000 ms 8428 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 989 ms 8340 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.