oj.uz

Submission #674778

# Submission time Handle Problem Language Result Execution time Memory
674778 2022-12-26T07:44:55 Z Valera_Grinenko Secret (JOI14_secret) C++17
0 / 100
 462 ms 4488 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 Secret(a, b); } // associative operation
	void fill(int l, int r, int ind) {
		if (ind < 0) return;
		int m = (l+r)/2;
		T prod = id;
    for(int i = m - 1; i >= l; i--) stor[i][ind] = prod = comb(a[i],prod);
		prod = id;
    for(int i = m; 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;
		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);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 2380 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 587608200.
2 Incorrect 117 ms 2384 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 709885984.
3 Incorrect 124 ms 2456 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 629483540.
4 Incorrect 447 ms 4380 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 34079308.
5 Incorrect 419 ms 4488 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 542818560.
6 Incorrect 431 ms 4316 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 579799611.
7 Incorrect 414 ms 4344 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 772352096.
8 Incorrect 462 ms 4284 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 290455552.
9 Incorrect 430 ms 4432 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 30940648.
10 Incorrect 432 ms 4396 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 810198025.