Submission #1290612

#TimeUsernameProblemLanguageResultExecution timeMemory
1290612monaxiaSecret (JOI14_secret)C++20
0 / 100
355 ms4444 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = (119 << 23) | 1;
constexpr ull sqr = 223;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random_ll(ll l, ll r) {if (l > r) return -1; return uniform_int_distribution<ll>(l, r)(rng);}

#include "secret.h"

int tre[25][1005], mask[1005];

int n;
int a[1001];

void inittt(int l, int r, int layer){
    if(l == r){
        tre[layer][l] = a[l];
        return;
    }

    int mid = (l + r) >> 1;

    tre[layer][mid] = a[mid];
    tre[layer][mid + 1] = a[mid + 1];

    for(int i = mid - 1; i >= l; i --){
        tre[layer][i] = Secret(a[i], tre[layer][i + 1]);
    } 

    for(int i = mid + 2; i <= r; i ++){
        tre[layer][i] = Secret(tre[layer][i - 1], a[i]);
    }

    inittt(l, mid, layer + 1);
    inittt(mid + 1, r, layer + 1);
}

void Init(int N, int A[]){
    memset(tre, 0, sizeof(tre));
    memset(mask, 0, sizeof(mask));
    n = N;

    for(int i = 1; i <= n; i ++) a[i] = A[i - 1];

    inittt(1, n, 1);
}

int Query(int l, int r){
    l ++;
    r ++;

    int u = 1, v = n, layer = 1;

    while(u != v){
        int mid = (u + v) >> 1;

        if(l <= mid && mid < r) {
            return Secret(tre[layer][l], tre[layer][r]);
        }

        if(mid < u) u = mid + 1;
        else v = mid;

        layer ++;
    }

    return a[l];
}
#Verdict Execution timeMemoryGrader output
Fetching results...