Submission #994328

#	Time	Username	Problem	Language	Result	Execution time	Memory
994328		nngan267	Secret (JOI14_secret)	C++17	0 / 100	321 ms	4480 KiB

secret

#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 / 100