oj.uz

Submission #971740

# Submission time Handle Problem Language Result Execution time Memory
971740 2024-04-29T08:41:55 Z Art_ogo Secret (JOI14_secret) C++17
0 / 100
 403 ms 4436 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e3+10, LG = 10;

int msk[MAXN];
int t[LG][MAXN];
int a[MAXN];
int n;


void build(int l, int r, int v){
    if(l == r){
        t[v][l] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    t[v][m] = a[m];
    msk[m] ^= 1 << v;
    for(int i = m - 1; i >= l; i--){
        t[v][i] = Secret(a[i], t[v][i + 1]);
        msk[i] ^= 1 << v;
    }
    t[v][m + 1] = a[m + 1];
    for(int i = m + 2; i <= r; i++)
        t[v][i] = Secret(t[v][i - 1], a[i]);
    build(l, m, v + 1);
    build(m + 1, r, v + 1);
}


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

int Query(int L, int R){
    if(L == R)
        return a[L];
    int cur = __builtin_ctz(msk[L]^msk[R]);
    return Secret(t[cur][L], t[cur][R]);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2648 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 109 ms 2720 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 2648 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Incorrect 372 ms 4384 KB Wrong Answer: Query(384, 458) - expected : 896057572, actual : 273916724.
5 Incorrect 372 ms 4432 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 307380480.
6 Incorrect 373 ms 4432 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 950550627.
7 Incorrect 403 ms 4268 KB Wrong Answer: Query(18, 983) - expected : 662702203, actual : 644453481.
8 Incorrect 379 ms 4436 KB Wrong Answer: Query(105, 938) - expected : 880895064, actual : 225943760.
9 Incorrect 375 ms 4268 KB Wrong Answer: Query(16, 936) - expected : 294129807, actual : 155585606.
10 Incorrect 374 ms 4264 KB Wrong Answer: Query(35, 864) - expected : 544031877, actual : 336773525.