oj.uz

Submission #762088

# Submission time Handle Problem Language Result Execution time Memory
762088 2023-06-20T18:48:21 Z beaboss Secret (JOI14_secret) C++14
100 / 100
 395 ms 4580 KB 
// https://oj.uz/problem/view/JOI14_secret
// 
#include "secret.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

int prefix[1000][1000];

const int MX = 2e5;

int dat[18][MX], mask[MX];

int x[MX];

void divi(int l, int r, int lev) {  // generate dat and mask for [l, r]
	if (l == r) return;
	int m = (l + r) / 2;
	dat[lev][m] = x[m]; // set default lefthand value

	for (int i = m-1; i >= l; i--) dat[lev][i] = Secret(x[i], dat[lev][i + 1]); // gen left hand values

	// same thing for right side
	dat[lev][m + 1] = x[m + 1];
	for (int i = m + 2; i <= r; i++) dat[lev][i] = Secret(dat[lev][i - 1], x[i]);


	for (int i = m + 1; i <= r; i++) mask[i] ^= 1 << lev; // signify with mask that these values we move right
	
	divi(l, m, lev + 1);
	divi(m + 1, r, lev + 1);
}


void Init(int N, int a[]) {
	FOR(i, 0, N) x[i] = a[i];
	divi(0, N-1, 0);
}

int Query(int l, int r) {
	if (l == r) return x[l];
	else {  // find level where info is stored
		// ctz gives number of trailing zeroes
		int bits = __builtin_ctz(mask[l] ^ mask[r]); // how many starting left/right movements are the same
		return Secret(dat[bits][l], dat[bits][r]);
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 2464 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 112 ms 2584 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 116 ms 2444 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 383 ms 4452 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 395 ms 4580 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 384 ms 4376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 384 ms 4356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 388 ms 4392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 384 ms 4440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 383 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1