oj.uz

답안 #376074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376074 2021-03-10T20:27:56 Z Leonardo_Paes 비밀 (JOI14_secret) C++17
30 / 100
 592 ms 6252 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;

std::map<pii, int> m;
std::set<pii> s;

class Seg{
public:
	int join(int a, int b){
		if(a == -1) return b;
		if(b == -1) return a;
		pii x = {a, b};
		if(s.find(x) == s.end()) m[x] = Secret(a, b), s.insert(x);
		return m[x];
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = v[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(2*node, l, mid), build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
	}
	int query(int node, int tl, int tr, int l, int r){
		if(tl > r or tr < l) return -1;
		if(tl >= l and tr <= r) return tree[node];
		int mid = (tl + tr) >> 1;
		return join(query(2*node, tl, mid, l, r), query(2*node+1, mid+1, tr, l, r));
	}
private:
	int tree[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);
	/*for(int l=1; l<=N/2; l++){
		for(int r=l+1; r<=N/2; r++){
			seg.query(1, 1, N, l, r);
		}
	}
	for(int l=N/2+1; l<=N; l++){
		for(int r=l+1; r<=N; r++){
			seg.query(1, 1, N, l, r);
		}
	}*/
}

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

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 174 ms 3820 KB Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 10
2 Partially correct 172 ms 3820 KB Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 12
3 Partially correct 181 ms 3820 KB Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 11
4 Partially correct 557 ms 6080 KB Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 13
5 Partially correct 549 ms 6252 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13
6 Partially correct 514 ms 5356 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4
7 Partially correct 592 ms 5828 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
8 Partially correct 543 ms 5740 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 15
9 Partially correct 557 ms 5872 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
10 Partially correct 552 ms 5868 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13