Submission #341850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341850	2020-12-31T08:27:26 Z	ronnith	Secret (JOI14_secret)	C++14	100 / 100	510 ms	4584 KB

secret

#include <bits/stdc++.h>
#include "secret.h"

#define FOR(i,a,b) for(int i = (a);i < (b);i ++)
#define ROF(i,a,b) for(int i = (a);i >= (b);i --)
#define trav(a, b) for(auto a : b)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define pb push_back
#define mk make_pair
#define f first
#define s second

using namespace std;

typedef long long ll;

int n;
int dat[11][1000];

void divi(int lvl, int lx, int rx, int *a){
	if(lx == rx){
		dat[lvl][lx] = a[lx];
		return;
	}
	int mid = lx + (rx - lx) / 2;
	ROF(i,mid,lx){
		if(i == mid)dat[lvl][i] = a[i];
		else dat[lvl][i] = Secret(a[i], dat[lvl][i + 1]);
	}
	FOR(i,mid + 1,rx + 1){
		if(i == mid + 1)dat[lvl][i] = a[i];
		else dat[lvl][i] = Secret(dat[lvl][i - 1], a[i]);
	}
	divi(lvl + 1, lx, mid, a);divi(lvl + 1, mid + 1, rx, a);
}

void Init(int N, int a[]) {
	n = N;
	divi(0,0,n - 1,a);
}

int query(int lvl, int l, int r, int lx, int rx){
	int mid = lx + (rx - lx) / 2;
	if(r >= mid && l <= mid){
		int res = dat[lvl][l];
		if(r > mid)res = Secret(res, dat[lvl][r]);
		return res;
	}
	if(r < mid)return query(lvl + 1, l, r, lx, mid);
	else return query(lvl + 1, l, r, mid + 1, rx);
}

int Query(int l, int r) {
	return query(0,l,r,0,n - 1);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	2412 KB	Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2	Correct	142 ms	2448 KB	Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3	Correct	143 ms	2412 KB	Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4	Correct	503 ms	4360 KB	Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5	Correct	506 ms	4332 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6	Correct	501 ms	4460 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7	Correct	507 ms	4460 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8	Correct	501 ms	4312 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9	Correct	510 ms	4332 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10	Correct	504 ms	4584 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1