oj.uz

Submission #25285

# Submission time Handle Problem Language Result Execution time Memory
25285 2017-06-21T05:52:48 Z 서규호(#1060) Secret (JOI14_secret) C++
100 / 100
 646 ms 9976 KB 
#include "secret.h"
#include <bits/stdc++.h>

int N,a[1002];
int where[1002][1002];
int memo[10][1002];

void divide(int lev,int s,int e){
	if(e-s <= 1) return;
	int mid = (s+e)/2;
	divide(lev+1,s,mid);
	divide(lev+1,mid+1,e);
	for(int i=s; i<=mid; i++){
		for(int j=mid+1; j<=e; j++){
			where[i][j] = lev;
		}
	}
	memo[lev][mid] = a[mid];
	for(int i=mid-1; i>=s; i--){
		memo[lev][i] = Secret(a[i],memo[lev][i+1]);
	}
	memo[lev][mid+1] = a[mid+1];
	for(int i=mid+2; i<=e; i++){
		memo[lev][i] = Secret(memo[lev][i-1],a[i]);
	}
}
void Init(int n, int A[]) {
	int N = n;
	for(int i=0; i<N; i++) a[i+1] = A[i];
	divide(1,1,N);
}

int Query(int l, int r) {
	l++; r++;
	if(l == r) return a[l];
	if(l+1 == r) return Secret(a[l],a[r]);
	int it = where[l][r];
	return Secret(memo[it][l],memo[it][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9976 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 9976 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 186 ms 9976 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 626 ms 9976 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 639 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 639 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 646 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 599 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 606 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 633 ms 9976 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1