oj.uz

답안 #396618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396618 2021-04-30T12:57:42 Z Aryan_Raina 비밀 (JOI14_secret) C++14
100 / 100
 520 ms 5444 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

map<pair<int,int>, int> mp;
template<class T, int SZ> struct RangeQuery {
	int n; 
	T stor[SZ][31-__builtin_clz(SZ)], id = 1;
	vector<T> a;
	T comb(T a, T b) { 
		if (mp.count({a, b})) return mp[{a,b}];
		if (mp.count({b, a})) return mp[{b,a}];
		return mp[{a,b}] = Secret(a, b); 
	}
	void fill(int l, int r, int ind) {
		if (ind < 0) return;
		int m = (l + r) >> 1;
		T pre = stor[m-1][ind] = a[m-1]; 
		for (int i = m-2; i >= l; i--) stor[i][ind] = pre = comb(a[i], pre);
		pre = stor[m][ind] = a[m]; 
		for (int i = m+1; i < r; i++) stor[i][ind] = pre = comb(pre, a[i]);
		fill(l, m, ind-1); fill(m, r, ind-1);
	}	
	void init() {
		n = 1; while ((1<<n) < a.size()) n++;
		a.resize(1<<n); fill(0, 1<<n, n-1);
	}
	T query(int l, int r) {
		if (l == r) return a[l];
		int t = 31-__builtin_clz(r^l);
		return comb(stor[l][t], stor[r][t]);
	}
};

RangeQuery<int, (1<<10)> rq;
void Init(int N, int A[]) {
	rq.a.resize(N);
	for (int i = 0; i < N; i++) {
		rq.a[i] = A[i];
	}
	rq.init();
}

int Query(int L, int R) {
  return rq.query(L, R);
}

Compilation message

secret.cpp: In instantiation of 'void RangeQuery<T, SZ>::init() [with T = int; int SZ = 1024]':
secret.cpp:41:10:   required from here
secret.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   n = 1; while ((1<<n) < a.size()) n++;

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 3164 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 3184 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 149 ms 3268 KB Output is correct - number of calls to Secret by Init = 3847, maximum number of calls to Secret by Query = 1
4 Correct 509 ms 5372 KB Output is correct - number of calls to Secret by Init = 7498, maximum number of calls to Secret by Query = 1
5 Correct 514 ms 5444 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 5164 KB Output is correct - number of calls to Secret by Init = 7512, maximum number of calls to Secret by Query = 1
7 Correct 520 ms 5324 KB Output is correct - number of calls to Secret by Init = 7509, maximum number of calls to Secret by Query = 1
8 Correct 513 ms 5316 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1
9 Correct 519 ms 5308 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1
10 Correct 516 ms 5344 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1