oj.uz

답안 #197877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197877 2020-01-24T02:05:32 Z Malomalomalomalo 비밀 (JOI14_secret) C++14
100 / 100
 599 ms 4600 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> a(1000 + 5);
int n;

struct node {
	node * c[2] = {nullptr, nullptr};
	int m,l,r;
	vector<int> val;
	void init(int l, int r){
		this->l = l;this->r = r;	
		m = (r+l)/2;
		val = vector<int>(r-l+1);
		val[m-l] = a[m];
		for(int i = m-1;i >= l; --i){
			val[i-l] = Secret(a[i], val[i+1-l]);
		}
		val[m+1-l] = a[m+1];
		for(int i = m+2;i <= r; ++i){
			val[i-l] = Secret(val[i-1-l], a[i]);
		}
		if(r-l+1 >= 5){
			c[0] = new node();
			c[1] = new node();
			if(m-l >= 2)c[0]->init(l,m-1);
			if(r-(m+1) >= 2)c[1]->init(m+2,r);
		}
	}
	int query(int L, int R){
		if(R <= m-1){
			return c[0]->query(L,R);
		}
		else if(L >= m+2){
			return c[1]->query(L,R);
		}
		else{
			assert(l <= L && r >= R);
			if(R == m)return val[L-l];
			else if(L == m + 1)return val[R-l];
			else return Secret(val[L-l],val[R-l]);
		}
	}
} root;

void Init(int N, int A[]) {
	n = N;
	for(int i = 0;i < n; ++i)a[i] = A[i];
	root.init(0,n-1);
}

int Query(int L, int R) {
	return (L == R ? a[L] : root.query(L,R));
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 2424 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 171 ms 2504 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 170 ms 2424 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 599 ms 4408 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 593 ms 4516 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 594 ms 4600 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 597 ms 4344 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 596 ms 4348 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 596 ms 4600 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 597 ms 4348 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1