oj.uz

Submission #553437

# Submission time Handle Problem Language Result Execution time Memory
553437 2022-04-25T20:08:48 Z Hanksburger Secret (JOI14_secret) C++17
100 / 100
 471 ms 8464 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int sum[1005][1005], val[1005], num;
void recur(int l, int r)
{
	if (l==r)
	{
		sum[l][l]=val[l];
		return;
	}
	int mid=(l+r)/2;
	sum[mid][mid]=val[mid];
	sum[mid+1][mid+1]=val[mid+1];
	for (int i=mid-1; i>=l; i--)
		sum[mid][i]=Secret(val[i], sum[mid][i+1]);
	for (int i=mid+2; i<=r; i++)
		sum[mid+1][i]=Secret(sum[mid+1][i-1], val[i]);
	recur(l, mid);
	recur(mid+1, r);
}
void Init(int n, int a[])
{
	num=n;
	for (int i=0; i<n; i++)
		val[i]=a[i];
	recur(0, n-1);
}
int Query(int l, int r)
{
	int a=0, b=num-1;
	while (a<b)
	{
		int mid=(a+b)/2;
		if (l<=mid && mid<r)
			return Secret(sum[mid][l], sum[mid+1][r]);
		else if (r<=mid)
			b=mid;
		else
			a=mid+1;
	}
	return sum[a][a];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4360 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 129 ms 4396 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 137 ms 4444 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 467 ms 8464 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 471 ms 8124 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 456 ms 8128 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 464 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 464 ms 8328 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 462 ms 8196 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 462 ms 8184 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1