oj.uz

Submission #752591

# Submission time Handle Problem Language Result Execution time Memory
752591 2023-06-03T09:23:00 Z jamezzz Secret (JOI14_secret) C++17
100 / 100
 520 ms 4420 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf

int n,a[1024],st[12][1024];

inline int ask(int x,int y){
	if(x==-1)return y;
	if(y==-1)return x;
	return Secret(x,y);
}

void build(int lvl,int l,int r){
	int m=(l+r)>>1;
	int pv=-1;
	for(int i=m;i>=l;--i){
		pv=st[lvl][i]=ask(a[i],pv);
	}
	pv=-1;
	for(int i=m+1;i<=r;++i){
		pv=st[lvl][i]=ask(pv,a[i]);
	}
	if(l+1==r)return;
	build(lvl-1,l,m);
	build(lvl-1,m+1,r);
}

void Init(int N,int A[]){
	n=N;
	for(int i=0;i<n;++i)a[i]=A[i];
	int lvl=31-__builtin_clz(n);
	int sz=n;
	if((1<<lvl)!=n)++lvl,sz=1<<lvl;
	for(int i=n;i<sz;++i)a[i]=-1;
	build(lvl-1,0,sz-1);
}

int Query(int L,int R){
	int lvl=31-__builtin_clz(L^R);
	return L==R?st[lvl][L]:ask(st[lvl][L],st[lvl][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2444 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 125 ms 2456 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 125 ms 2508 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 451 ms 4300 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 438 ms 4380 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 447 ms 4348 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 465 ms 4420 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 499 ms 4360 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 520 ms 4352 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 475 ms 4340 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1