oj.uz

Submission #605825

# Submission time Handle Problem Language Result Execution time Memory
605825 2022-07-26T02:55:57 Z TranGiaHuy1508 Secret (JOI14_secret) C++17
100 / 100
 440 ms 4548 KB 
#include <bits/stdc++.h>
using namespace std;

#include "secret.h"

namespace local{
	vector<int> v;

	struct Node{
		int l, r;
		vector<int> V;

		Node() = default;
		Node(int L, int R): l(L), r(R) {
			V.resize(r - l + 1);
			int m = (l + r) / 2;

			V[m - l] = v[m]; V[m - l + 1] = v[m+1];

			for (int i = m - l - 1; i >= 0; i--) V[i] = Secret(v[i+l], V[i+1]);
			for (int i = m - l + 2; i < r - l + 1; i++) V[i] = Secret(V[i-1], v[i+l]);
		}
	};

	struct Segtree{
		vector<Node> tree;
		int _n;

		Segtree() = default;
		Segtree(int N): tree(4*N), _n(N) {
			build(1, 0, N-1);
		}

		void build(int i, int l, int r){
			tree[i] = Node(l, r);
			if (l == r) return;
			int m = (l + r) / 2;
			build(i<<1, l, m);
			build(i<<1|1, m+1, r);
		}

		int get(int tl, int tr) { return get(1, 0, _n - 1, tl, tr); }
		int get(int i, int l, int r, int tl, int tr){
			int m = (l + r) / 2;
			if (l == r) return tree[i].V[0];
			if (tl <= m && m < tr) return Secret(tree[i].V[tl-l], tree[i].V[tr-l]);
			if (tr <= m) return get(i<<1, l, m, tl, tr);
			return get(i<<1|1, m+1, r, tl, tr);
		}
	} st;
}

void Init(int N, int A[]){
	local::v.resize(N);
	for (int i = 0; i < N; i++) local::v[i] = A[i];
	local::st = local::Segtree(N);
}

int Query(int L, int R){
	return local::st.get(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 2356 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 124 ms 2360 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 117 ms 2564 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 414 ms 4536 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 425 ms 4424 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 419 ms 4408 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 439 ms 4456 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 422 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 440 ms 4548 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 419 ms 4456 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1