oj.uz

답안 #376672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376672 2021-03-12T00:40:34 Z Leonardo_Paes 비밀 (JOI14_secret) C++17
100 / 100
 540 ms 4716 KB 
#include "secret.h"
#include <bits/stdc++.h>

typedef std::pair<int,int> pii;
#define f first
#define s second
const int maxn = 1030;
int v[maxn], n;

class Seg{
public:
	void build(int node, int l, int r){
		if(l == r){
			pref[node].push_back(v[l]);
			return;
		}
		int mid = (l + r) >> 1;
		int val;
		for(int i=mid; i>=l; i--){
			if(i == mid) suf[node].push_back(val = v[i]);
			else suf[node].push_back(val = Secret(v[i], val));
		}
		for(int i=mid+1; i<=r; i++){
			if(i == mid+1) pref[node].push_back(val = v[i]);
			else pref[node].push_back(val = Secret(val, v[i]));
		}
		build(2*node, l, mid), build(2*node+1, mid+1, r);
	}
	int query(int node, int tl, int tr, int l, int r){
		int mid = (tl + tr) >> 1;
		if(tl == tr) return pref[node].front();
		if(l <= mid and mid+1 <= r){
			return Secret(suf[node][mid - l], pref[node][r - mid - 1]);
		}
		else if(l >= mid+1) return query(2*node+1, mid+1, tr, l, r);
		else return query(2*node, tl, mid, l, r);
	}
private:
	std::vector<int> pref[2*maxn], suf[2*maxn];
}seg;

void Init(int N, int A[]) {
	n = N;
	for(int i=1; i<=N; i++) v[i] = A[i-1];
	seg.build(1, 1, n);
}

int Query(int L, int R) {
	L++, R++;
	return seg.query(1, 1, n, L, R);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 2540 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2796 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 2540 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 508 ms 4588 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 518 ms 4652 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 540 ms 4612 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 509 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 513 ms 4716 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 512 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1