Submission #605825

#	Time	Username	Problem	Language	Result	Execution time	Memory
605825		TranGiaHuy1508	Secret (JOI14_secret)	C++17	100 / 100	440 ms	4548 KiB

secret

#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 / 100