oj.uz

Submission #1086193

# Submission time Handle Problem Language Result Execution time Memory
1086193 2024-09-09T17:24:01 Z f0rizen Secret (JOI14_secret) C++17
100 / 100
 314 ms 4496 KB 
#include "secret.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T, class F = function<T(T, T)>>
struct DST {
    static const int lg = 10;

    vector<int> a;
    array<vector<int>, lg> st;
    vector<int> mask;
    F func;

    DST() {}
    DST(const vector<int> &_a, const F &f) : a(_a), func(f) {
        int n = a.size();
        for (int i = 0; i < lg; ++i) {
            st[i].resize(n);
        }
        mask.resize(n);
        build(0, n - 1, 0);
    }

    void build(int l, int r, int k) {
        if (l == r) {
            return;
        }
        int mid = (l + r) / 2;
        st[k][mid] = a[mid];
        for (int i = mid - 1; i >= l; --i) {
            st[k][i] = func(a[i], st[k][i + 1]);
        }
        st[k][mid + 1] = a[mid + 1];
        for (int i = mid + 2; i <= r; ++i) {
            st[k][i] = func(st[k][i - 1], a[i]);
        }
        for (int i = mid + 1; i <= r; ++i) {
            mask[i] ^= (1 << k);
        }
        build(l, mid, k + 1);
        build(mid + 1, r, k + 1);
    }

    // [l, r]
    int get(int l, int r) {
        if (l == r) {
            return a[l];
        }
        int k = __builtin_ctz(mask[l] ^ mask[r]);
        return func(st[k][l], st[k][r]);
    }
};

DST<int> dst;

void Init(int N, int A[]) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        a[i] = A[i];
    }
    dst = DST<int>(a, [](int a, int b) {
        return Secret(a, b);
    });
}

int Query(int L, int R) {
    return dst.get(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2404 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 85 ms 2384 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 85 ms 2384 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 306 ms 4480 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 307 ms 4468 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 312 ms 4496 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 301 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 314 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 314 ms 4328 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 306 ms 4384 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1