oj.uz

Submission #994330

# Submission time Handle Problem Language Result Execution time Memory
994330 2024-06-07T11:21:33 Z vjudge1 Secret (JOI14_secret) C++14
0 / 100
 339 ms 4496 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pll pair<ll, ll>
#define vi vector<int>
#define db long double

const int maxn = 1e6+5;
const ll mod = 1e9+7;
const ll inf = 1e18;
const double eps = 1e-9;
const double pi = acos(-1);
const int block_size = 320;

#include "secret.h"

int n, a[1005];
ll acc[15][1005];
int mask[1005];

void cal(int lev, int l, int r){
    if(l == r) return;
    int mid = (l+r)/2;

    acc[lev][mid] = a[mid];
    for(int i=mid-1; i>=l; i--){
        acc[lev][i] = Secret(acc[lev][i+1], a[i]);
    }
    acc[lev][mid+1] = a[mid+1];
    for(int i=mid+2; i<=r; i++){
        acc[lev][i] = Secret(acc[lev][i-1], a[i]);
    }

    for(int i=mid+1; i<=r; i++){
        mask[i] |= (1<<lev);
    }

    cal(lev+1, l, mid);
    cal(lev+1, mid+1, r);
}

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

int Query(int l, int r){
    if(l == r) return a[l];
    int lvl = __builtin_ctz(mask[l] ^ mask[r]);
    return Secret(acc[lvl][l], acc[lvl][r]);
}

//int main(){
//    freopen("ngan.inp", "r", stdin);
//    freopen("ngan.out", "w", stdout);
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    int test; cin >> test;
//    while(test--){
//        solve();
//    }
//
//}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 2652 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 88 ms 2756 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 96 ms 2652 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 326 ms 4432 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 314 ms 4496 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 308 ms 4436 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 154975445.
7 Incorrect 319 ms 4496 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 339 ms 4468 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 312 ms 4272 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 317 ms 4432 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.