oj.uz

Submission #674792

# Submission time Handle Problem Language Result Execution time Memory
674792 2022-12-26T08:25:59 Z Valera_Grinenko Secret (JOI14_secret) C++17
0 / 100
 431 ms 4316 KB 
#include "secret.h"
#include <vector>
using namespace std;

template<class T> struct onlineDQ {
  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) {
      stor[l][ind] = a[l];
      return;
    }
		int m = (l+r)/2;
    stor[m][ind] = a[m];
    for(int i = m - 1; i >= l; i--) stor[i][ind] = comb(a[i], stor[i + 1][ind]);
    stor[m + 1][ind] = a[m + 1];
    for(int i = m + 2; i < r; i++) stor[i][ind] = comb(stor[i - 1][ind] ,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]);
	}
};

onlineDQ<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(493, 496) - expected : 990344084, actual : 692145173.
2 Incorrect 110 ms 2368 KB Wrong Answer: Query(236, 238) - expected : 173116186, actual : 800141843.
3 Incorrect 111 ms 2380 KB Wrong Answer: Query(130, 131) - expected : 127065177, actual : 411394072.
4 Incorrect 414 ms 4204 KB Wrong Answer: Query(216, 220) - expected : 518824820, actual : 467952034.
5 Incorrect 411 ms 4280 KB Wrong Answer: Query(584, 592) - expected : 111053842, actual : 895372370.
6 Incorrect 414 ms 4284 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 966582165.
7 Partially correct 431 ms 4276 KB Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1
8 Partially correct 414 ms 4252 KB Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1
9 Partially correct 424 ms 4316 KB Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1
10 Partially correct 414 ms 4316 KB Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1