oj.uz

Submission #961387

# Submission time Handle Problem Language Result Execution time Memory
961387 2024-04-12T03:06:09 Z ByeWorld Secret (JOI14_secret) C++14
100 / 100
 392 ms 5004 KB 
#include "secret.h"
#include <bits/stdc++.h>
#include <random>
#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,pii> ipii;
const ll MAXN = 1e3+10;
const ll MAXA = 1e6+10;
const ll INF = 2e18+10;
const ll LOG = 30;
const ll MOD = 1e9+7;

ll n;
ll a[MAXN], dep[MAXN];
map <pii, ll> m;

void bd(ll DEP, ll l, ll r){
	if(l>r) return;
	// cout << DEP << ' ' << l << ' ' << r << " pp\n";
	ll mid = md;
	dep[mid] = DEP;
	if(l==r) return;

	ll val = a[mid];
	for(ll i=mid-1; i>=l; i--){
		val = Secret(a[i], val); // ke kiri
		m[pii(i, mid)] = val;
	}
	val = a[mid+1];
	for(ll i=mid+2; i<=r; i++){
		val = Secret(val, a[i]); // ke kanan
		m[pii(mid+1, i)] = val;
	}
	bd(DEP+1, l, mid-1); bd(DEP+1, mid+1, r);
}

void Init(int N, int x[]) {
	n = N;
	for(ll i=0; i<n; i++){
		a[i+1] = x[i]; m[pii(i+1, i+1)] = x[i];
	}
	bd(1, 1, n);
	// for(ll i=1; i<=n; i++) cout << dep[i] << " \n"[i==n];
}

int Query(int L, int R) {
	L++; R++;
	ll idx = -1, mn = INF;
	for(ll i=L; i<=R; i++){
		if(mn > dep[i]){
			idx = i;
			mn = dep[i];
		}
	}
	if(idx==R) return m[pii(L, R)];
	return (int)Secret(m[pii(L, idx)], m[pii(idx+1, R)]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 2900 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 110 ms 2736 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 114 ms 2904 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 380 ms 5004 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 381 ms 4920 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 381 ms 4948 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 383 ms 4768 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 392 ms 4772 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 392 ms 4772 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 389 ms 4768 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1