oj.uz

Submission #29737

# Submission time Handle Problem Language Result Execution time Memory
29737 2017-07-20T11:53:18 Z cdemirer Secret (JOI14_secret) C++14
100 / 100
 629 ms 9920 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int _N;
int _A[1000];
int hesaplar[1000][1000];

void calc(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l+r)/2;
	if (r - l == 1) {
		hesaplar[mid][mid+1] = Secret(_A[mid], _A[mid+1]);
		hesaplar[mid+1][mid] = _A[mid];
		return;
	}
	calc(l, mid-1);
	calc(mid+1, r);
	int lmid = (l+mid-1)/2, rmid = (mid+1+r)/2;
	if (mid-1 > lmid) hesaplar[mid][mid-1] = _A[mid-1];
	for (int i = mid-2; i > lmid; i--) {
		hesaplar[mid][i] = Secret(_A[i], hesaplar[mid][i+1]);
	}
	if (lmid == mid-1) {
		hesaplar[mid][lmid] = _A[lmid];
	}
	else {
		hesaplar[mid][lmid] = Secret(_A[lmid], hesaplar[mid][lmid+1]);
	}
	for (int i = lmid-1; i >= l; i--) {
		//cerr << "A" << endl;
		//cerr << "lmid, i, mid, lmid+1 : " << lmid << " " << i << " " << mid << " " << mid+1 << endl;
		hesaplar[mid][i] = Secret(hesaplar[lmid][i], hesaplar[mid][lmid]);
		//cerr << "B" << endl;
	}
	for (int i = mid+1; i < rmid; i++) {
		hesaplar[mid][i] = Secret(hesaplar[mid][i-1], _A[i]);
	}
	for (int i = rmid; i <= r; i++) {
		hesaplar[mid][i] = Secret(hesaplar[mid][rmid-1], hesaplar[rmid][i]);
	}
}

void Init(int N, int A[]) {
	memset(hesaplar, -1, sizeof(hesaplar));
	_N = N;
	for (int i = 0; i < N; i++) _A[i] = A[i];
	for (int i = 0; i < N; i++) hesaplar[i][i] = _A[i];
	calc(0, _N-1);
}

int Query(int L, int R) {
	int l = 0, r = _N-1;
	while (true) {
		//cerr << l << " " << r << " : " << L << " " << R << endl;
		int mid = (l+r)/2;
		if (L == R && L == mid) return _A[mid];
		else if (L < mid && R >= mid) {
			int a = hesaplar[mid][L];
			int b = hesaplar[mid][R];
			return Secret(a, b);
		}
		else if (R == mid) {
			return Secret(hesaplar[mid][L], _A[mid]);
		}
		else if (R == mid-1) {
			return hesaplar[mid][L];
		}
		else if (L == mid) {
			return hesaplar[mid][R];
		}
		else if (R < mid) {
			r = mid-1;
		}
		else if (L > mid) {
			l = mid+1;
		}
		else {
			cerr << "Impossible branch" << endl;
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9920 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 159 ms 9920 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 169 ms 9920 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 609 ms 9920 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 609 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 606 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 619 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 629 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 599 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 603 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1