# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964562 | angella | Secret (JOI14_secret) | C++17 | 383 ms | 19388 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
#include "secret.h"
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 3e5+23, lg = 18;
int t, n, a[N];
vector<int> pr[N], sf[N];
void build(int ind, int lc, int rc) {
if(lc>=rc-1) return;
int mid = (lc+rc)/2;
pr[ind].pb(a[mid]);
for(int i=mid+1; i<rc; i++) pr[ind].pb(Secret(a[i], pr[ind][i-mid-1]));
sf[ind].pb(a[mid-1]);
for(int i=mid-2; i>=lc; i--) sf[ind].pb(Secret(a[i], sf[ind][mid-1-i-1]));
build(2*ind, lc, mid); build(2*ind+1, mid, rc);
}
void Init(int _n, int _a[]) {
n = _n;
for(int i=1; i<=_n; i++) a[i] = _a[i-1];
build(1, 1, n+1);
}
int qry(int l, int r, int ind, int lc, int rc) {
int mid = (lc+rc)/2;
int sz1=mid-l,sz2=r-mid;
if(r == mid) return sf[ind][sz1-1];
if(l == mid) return pr[ind][sz2-1];
if(r<=mid) return qry(l, r, 2*ind, lc, mid);
if(l>=mid) return qry(l, r, 2*ind+1, mid, rc);
return Secret(sf[ind][sz1-1], pr[ind][sz2-1]);
}
int Query(int l, int r) {
l++, r++;
if(l == r) return a[l];
int res = qry(l, r+1, 1, 1, n+1);
//cout<<res<<endl;
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |