oj.uz

Submission #52505

# Submission time Handle Problem Language Result Execution time Memory
52505 2018-06-26T06:18:43 Z tataky(#1353) Secret (JOI14_secret) C++11
30 / 100
 684 ms 6988 KB 
#include "secret.h"
#include <map>
#include <utility>

using namespace std;

typedef pair<int, int> ip;

int sp[10][1001], to[10][1001], n;
int a[1001];
map<ip, int> d;

int Query(int L, int R) {
	if (L == R) return a[L];
	int len = R - L + 1;
	int ret, cur = L;
	bool fst = true;
	for (int h = 9; h >= 0; h--) if (len&(1 << h)) {
		if (fst) {
			ret = sp[h][cur];
			cur = to[h][cur] + 1;
			fst = false;
		}
		else {
			if (d.count(ip(ret, sp[h][cur]))) ret = d[ip(ret, sp[h][cur])];
			else ret = d[ip(ret, sp[h][cur])] = Secret(ret, sp[h][cur]);
			cur = to[h][cur] + 1;
		}
	}
	return ret;
}

void setsparse() {
	for (int i = 0; i < n; i++) {
		sp[0][i] = a[i];
		to[0][i] = i;
	}
	for (int h = 1; h <= 9; h++) {
		for (int i = 0; i < n; i++) if (i + (1 << h) - 1< n) {
			to[h][i] = to[h - 1][to[h - 1][i] + 1];
			sp[h][i] = Secret(sp[h - 1][i], sp[h - 1][to[h - 1][i] + 1]);
			d[ip(sp[h - 1][i], sp[h - 1][to[h - 1][i] + 1])] = sp[h][i];
		}
	}
}

void Init(int N, int A[]) {
	n = N;
	for (int i = 0; i < n; i++)
		a[i] = A[i];
	setsparse();
}

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:16:6: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ret, cur = L;
      ^~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 222 ms 4080 KB Output is partially correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 7
2 Partially correct 216 ms 4328 KB Output is partially correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 7
3 Partially correct 199 ms 4328 KB Output is partially correct - number of calls to Secret by Init = 3604, maximum number of calls to Secret by Query = 7
4 Partially correct 660 ms 6900 KB Output is partially correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 8
5 Partially correct 642 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
6 Partially correct 628 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 2
7 Partially correct 643 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
8 Partially correct 631 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 6
9 Partially correct 684 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
10 Partially correct 628 ms 6988 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 7