Submission #207767

#	Time	Username	Problem	Language	Result	Execution time	Memory
207767		mode149256	Secret (JOI14_secret)	C++14	100 / 100	544 ms	12464 KiB

secret

/*input

*/
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

int Nas;
vii pref(1000, vi(1000));
vii suff(1000, vi(1000));
vb did(1000, false);
vi sk;

void make(int l, int r) {
	int m = (l + r) / 2;
	if (did[m]) return;
	did[m] = true;
	if (r - l <= 1) return;

	suff[m][m] = sk[m];
	if (l <= m - 1)
		suff[m - 1][m] = Secret(sk[m - 1], sk[m]);

	for (int i = m - 2; l <= i; i--)
		suff[i][m] = Secret(sk[i], suff[i + 1][m]);

	pref[m + 1][m + 1] = sk[m + 1];
	if (m + 2 <= r)
		pref[m + 1][m + 2] = Secret(sk[m + 1], sk[m + 2]);

	for (int i = m + 3; i <= r; ++i)
		pref[m + 1][i] = Secret(pref[m + 1][i - 1], sk[i]);

	make(l, m);
	make(m + 1, r);
}


void Init(int N, int A[]) {
	Nas = N;
	sk.resize(N);
	for (int i = 0; i < N; ++i)
		sk[i] = A[i];
	make(0, N - 1);
}

int Query(int L, int R) {
	if (L == R) return sk[L];
	if (L + 1 == R) return Secret(sk[L], sk[R]);
	int l = 0, r = Nas - 1;

	// printf("L = %d, R = %d\n", L, R);
	while (l < r) {
		// printf("l = %d, r = %d\n", l, r);
		int m = (l + r) / 2;
		if (L <= m and m + 1 <= R) {
			return Secret(suff[L][m], pref[m + 1][R]);
		}
		else if (m < L) l = m + 1;
		else r = m;
	}

	return -1;
}

• Subtask 1: 100 / 100