oj.uz

답안 #971739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971739 2024-04-29T08:34:42 Z Art_ogo 비밀 (JOI14_secret) C++17
0 / 100
 1147 ms 4692 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 >= 0; 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 < n; 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 2896 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 857017776.
2 Incorrect 287 ms 2856 KB Wrong Answer: Query(102, 157) - expected : 32612619, actual : 910332073.
3 Incorrect 297 ms 2652 KB Wrong Answer: Query(334, 369) - expected : 363022362, actual : 606595196.
4 Incorrect 1118 ms 4536 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 391790660.
5 Incorrect 1137 ms 4548 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 307380480.
6 Incorrect 1147 ms 4612 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 950550627.
7 Incorrect 1102 ms 4436 KB Wrong Answer: Query(30, 947) - expected : 556794905, actual : 667040792.
8 Incorrect 1108 ms 4532 KB Wrong Answer: Query(60, 907) - expected : 746620928, actual : 427894024.
9 Incorrect 1119 ms 4692 KB Wrong Answer: Query(6, 880) - expected : 164102475, actual : 22951435.
10 Incorrect 1102 ms 4604 KB Wrong Answer: Query(74, 915) - expected : 807897669, actual : 70700745.