oj.uz

Submission #25255

# Submission time Handle Problem Language Result Execution time Memory
25255 2017-06-21T04:56:19 Z 김동현(#1058) Secret (JOI14_secret) C++14
100 / 100
 646 ms 9204 KB 
#include "secret.h"
#include <algorithm>
using namespace std;

const int sz = 1024;
struct Seg{
	int dat[sz][sz];
	void ini(int n, int a[]){
		for(int i = 0; i < n; i++) dat[i][i] = a[i];
		for(int i = 2; i <= sz; i *= 2){
			for(int j = 0; j < 1000; j += i){
				if(j + i / 2 >= 1000) break;
				for(int k = j + i / 2 - 2; k >= j; k--) dat[k][j + i / 2 - 1] = Secret(a[k], dat[k + 1][j + i / 2 - 1]);
				for(int k = j + i / 2 + 1; k <= min(999, j + i - 1); k++) dat[j + i / 2][k] = Secret(dat[j + i / 2][k - 1], a[k]);
			}
		}
	}
	int get(int s, int e){
		if(s == e) return dat[s][s];
		int S = 0, E = sz - 1;
		while(true){
			int m = (S + E) / 2;
			if(s <= m && e <= m) E = m;
			else if(s > m && e > m) S = m + 1;
			else break;
		}
		return Secret(dat[s][(S + E) / 2], dat[(S + E) / 2 + 1][e]);
	}
} S;

void Init(int N, int A[]) {
	S.ini(N, A);
}

int Query(int L, int R) {
	return S.get(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
2 Correct 183 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
3 Correct 199 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
4 Correct 629 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
5 Correct 626 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 626 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
7 Correct 646 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 596 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 636 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 619 ms 9204 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1