Submission #70289

#	Time	Username	Problem	Language	Result	Execution time	Memory
70289		ivan100sic	Secret (JOI14_secret)	C++14	6 / 100	755 ms	4600 KiB

secret

#include <algorithm>
#include <iostream>
using namespace std;

int Secret(int, int);
const int I = 1024;
int p[10][I], s[10][I], a[I];

int resi(int l, int r, int i, int xl, int xr) {
	i--;
	int xm = (xl + xr) / 2, y;
	// l <= xm, xm+1 <= r

	if (xm-1 < l)
		y = resi(l, r, i, xm, xr);
	else if (xm > r)
		y = resi(l, r, i, xl, xm);
	else {
		// cerr << i << ' ' << xl << ' ' << xr << '\n';
		y = Secret(s[i][l], p[i][r]);
	}
	return y;
}

int Query(int L, int R) {
	return R-L ? resi(L, R, 10, 0, 1024) : a[L];
}

void Init(int N, int* A) {
	copy(A, A+N, a);
	copy(a, a+I, p[0]);
	copy(a, a+I, s[0]);
	for (int i=1; i<=9; i++) {
		int u = 1 << i, v = u / 2;
		for (int j=0; j<I; j+=u) {
			copy(p[i-1]+j, p[i-1]+j+v, p[i]+j);
			copy(s[i-1]+j+v, s[i-1]+j+u, s[i]+j+v);
			for (int k=j+v; k<j+u; k++)
				p[i][k] = Secret(p[i][k-1], a[k]);
			for (int k=j+v; k>j; k--)
				s[i][k-1] = Secret(a[k-1], s[i][k]);
		}
	}
}

/*
int main() {
	int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	Init(10, a);
	cout << Query(1, 1) << "\n"; // 2
	cout << Query(2, 2) << "\n"; // 3
	cout << Query(0, 9) << "\n"; // 55
	cout << Query(0, 1023) << "\n"; // 55
	cout << Query(1, 4) << "\n"; // 14
	cout << Query(5, 6) << "\n"; // 13
	cout << Query(6, 7) << "\n"; // 15
}

int Secret(int x, int y) {
	return x + y;
}
*/

• Subtask 1: 6 / 100