oj.uz

Submission #853163

# Submission time Handle Problem Language Result Execution time Memory
853163 2023-09-23T14:53:10 Z epicci23 Secret (JOI14_secret) C++17
100 / 100
 412 ms 4712 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
 
int t[10][1001],msk[1001],b[1001];
 
void build(int x, int l, int r, int a[])
{
	if(l>=r)return;
	int mid=(l+r)/2;
	t[x][mid]=a[mid];
	for(int i=mid-1;i>=l;i--)
		t[x][i]=Secret(a[i],t[x][i+1]);
	
	t[x][mid+1]=a[mid+1];
	msk[mid+1]|=(1<<x);
	for(int i=mid+2;i<=r;i++)
	{
		t[x][i]=Secret(t[x][i-1],a[i]);
		msk[i]|=(1<<x);
	}
	build(x+1,l,mid,a);
	build(x+1,mid+1,r,a);
}
 
void Init(int n, int a[])
{
	for(int i=0;i<n;i++)b[i]=a[i];
	build(0,0,n-1,a);
}
 
int Query(int l, int r)
{
	if(l==r) return b[l];
	int z=__builtin_ctz(msk[l]^msk[r]);
	return Secret(t[z][l],t[z][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2808 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 120 ms 2812 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 110 ms 2828 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 388 ms 4356 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 392 ms 4360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 388 ms 4712 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 386 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 386 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 412 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 382 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1