oj.uz

Submission #642049

# Submission time Handle Problem Language Result Execution time Memory
642049 2022-09-18T10:54:14 Z ymm Secret (JOI14_secret) C++17
100 / 100
 489 ms 12432 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static int n, *a;
static int seg[5010][2010];

static void init(int i, int b, int e)
{
	if (e-b == 1) {
		seg[i][b] = a[b];
		return;
	}
	int m = (b+e)/2;
	init(2*i+1, b, m);
	init(2*i+2, m, e);
	seg[i][m] = a[m];
	Loop (j,m+1,e)
		seg[i][j] = Secret(seg[i][j-1], a[j]);
	seg[i][m-1] = a[m-1];
	LoopR (j,b,m-1)
		seg[i][j] = Secret(a[j], seg[i][j+1]);
}

void Init(int N, int A[]) {
	n = N; a = A;
	init(0, 0, n);
}

static int query(int l, int r, int i, int b, int e)
{
	int m = (b+e)/2;
	if (l <= m && m <= r) {
		if (m == r)
			return seg[i][l];
		if (m == l)
			return seg[i][r-1];
		return Secret(seg[i][l], seg[i][r-1]);
	}
	if (r < m)
		return query(l, r, 2*i+1, b, m);
	else
		return query(l, r, 2*i+2, m, e);
}

int Query(int L, int R) {
	return query(L, R+1, 0, 0, n);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 6552 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 148 ms 6452 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 131 ms 6512 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 482 ms 12380 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 470 ms 12392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 477 ms 12432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 489 ms 12420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 449 ms 12416 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 471 ms 12348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 487 ms 12404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1