Submission #1291526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291526		sula2	Secret (JOI14_secret)	C++20	0 / 100	336 ms	4488 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> 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);
    vector<int> _a(n);
    for (int i = 0; i < n; i++)
        _a[i] = a[i];
    init(0, n-1, _a);
}

int Query(int l, int r) {
    for (int d = 0; d < 20; d++) {
        for (int mid : mids[d]) {
            if (l <= mid && mid <= r) {
                return Secret(lay[d][l], lay[d][r]);
            }
        }
    }
    return 1;
}

• Subtask 1: 0 / 100