oj.uz

답안 #674806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674806 2022-12-26T08:37:28 Z Valera_Grinenko 비밀 (JOI14_secret) C++17
100 / 100
 433 ms 4368 KB 
#include "secret.h"
#include <vector>
using namespace std;

template<class T> struct offlineDQ {
  static const int SZ = (1 << 10);
  int n;
  T stor[SZ][32-__builtin_clz(SZ)], id = 1;
	vector<T> a;
	T comb (T a, T b) { return (a == -1 ? b : (b == -1 ? a : Secret(a, b))); } // associative operation
	void fill(int l, int r, int ind) {
		if (ind < 0) return;
		int m = (l+r)/2;
		T prod = a[m - 1];
    if(l <= m - 1) stor[m - 1][ind] = prod;
    for(int i = m - 2; i >= l; i--) stor[i][ind] = prod = comb(a[i],prod);
		prod = a[m];
    if(m < r) stor[m][ind] = prod;
    for(int i = m + 1; i < r; i++) stor[i][ind] = prod = comb(prod,a[i]);
		fill(l,m,ind-1); fill(m,r,ind-1);
	}
	void init() {
		n = 1; while ((1<<n) < (int)a.size()) ++n;
    while(a.size() < (1 << n)) a.push_back(-1);
    // 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]);
	}
};

offlineDQ<int> odq;

void Init(int N, int A[]) {
  odq.a.resize(N);
  for(int i = 0; i < N; i++) odq.a[i] = A[i];
  odq.init();
}

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

Compilation message

secret.cpp: In instantiation of 'void offlineDQ<T>::init() [with T = int]':
secret.cpp:40:12:   required from here
secret.cpp:24:20: warning: comparison of integer expressions of different signedness: 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while(a.size() < (1 << n)) a.push_back(-1);
      |           ~~~~~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 2360 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 120 ms 2316 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 123 ms 2352 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 431 ms 4264 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 422 ms 4220 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 425 ms 4260 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 422 ms 4336 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 433 ms 4312 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 422 ms 4368 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 425 ms 4288 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1