oj.uz

Submission #134322

# Submission time Handle Problem Language Result Execution time Memory
134322 2019-07-22T12:38:16 Z someone_aa Secret (JOI14_secret) C++17
100 / 100
 618 ms 12604 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
int prefix[maxn][maxn];
int suffix[maxn][maxn];
int arr[maxn], n;

void precompute(int l, int r) {
	if(l > r) return;
	if(l == r) return;
	else {
		int mid = (l + r) / 2;

		//cout<<mid<<" ";

		suffix[mid][mid] = arr[mid];
		prefix[mid][mid+1] = arr[mid+1];

		for(int i=mid-1;i>=l;i--) {
			suffix[mid][i] = Secret(arr[i], suffix[mid][i+1]);
		}

		for(int i=mid+2;i<=r;i++) {
			prefix[mid][i] = Secret(prefix[mid][i-1], arr[i]);
		}

		precompute(l, mid);
		precompute(mid+1,r);
	}
}

void Init(int N, int A[]) {
	n = N;
	for(int i=0;i<n;i++) {
		arr[i] = A[i];
	}
	precompute(0, n-1);
}

int solve(int ql, int qr, int li=0, int ri=n-1) {
	if(li == ri) return arr[li];
	else {
		int mid = (li + ri) / 2;

		if(ql <= mid && qr > mid) {
			//cout<<"Here: ["<<li<<", "<<ri<<"] - ";
			//cout<<suffix[mid][ql]<<" "<<prefix[mid][qr]<<"\n";
			return Secret(suffix[mid][ql], prefix[mid][qr]);
		}
		else if(qr <= mid) {
			return solve(ql, qr, li, mid);
		}
		else {
			return solve(ql, qr, mid+1, ri);
		}
	}
}

int Query(int L, int R) {
  	return solve(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 6520 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 176 ms 6520 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 6648 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 615 ms 12292 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 602 ms 12348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 605 ms 12500 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 605 ms 12344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 605 ms 12356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 602 ms 12360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 618 ms 12604 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1