Submission #1291537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291537		sula2	Secret (JOI14_secret)	C++20	100 / 100	338 ms	4484 KiB

secret

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
#include "secret.h"

vector<int> _a;
vector<int> lay[20];
vector<int> mids[20];

void init(int l, int r, vector<int>& a, int dep = 0) {
    if (l == r) return;
    int mid = (l+r)/2;
    mids[dep].push_back(mid);
    lay[dep][mid] = a[mid];
    lay[dep][mid+1] = a[mid+1];
    for (int i = mid-1; i >= l; i--)
        lay[dep][i] = Secret(a[i], lay[dep][i+1]);
    for (int i = mid+2; i <= r; i++)
        lay[dep][i] = Secret(lay[dep][i-1], a[i]);
    init(l, mid, a, dep + 1);
    init(mid+1, r, a, dep + 1);
}

void Init(int n, int* a) {
    for (int i = 0; i < 20; i++)
        lay[i].resize(n);
    _a.resize(n);
    for (int i = 0; i < n; i++)
        _a[i] = a[i];
    init(0, n-1, _a);
}

int query(int l, int r, int ql, int qr, int dep = 0) {
    int mid = (l+r)/2;
    if (ql <= mid+1 && mid <= qr) {
        if (ql == mid+1)
            return lay[dep][qr];
        if (qr == mid)
            return lay[dep][ql];
        return Secret(lay[dep][ql], lay[dep][qr]);
    }
    if (qr < mid)
        return query(l, mid, ql, qr, dep + 1);
    else
        return query(mid+1, r, ql, qr, dep + 1);
}

int Query(int l, int r) {
    if (l == r) return _a[l];
    return query(0, _a.size()-1, l, r);
}

• Subtask 1: 100 / 100