Submission #109195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
109195	2019-05-05T12:10:41 Z	maruii	Secret (JOI14_secret)	C++14	0 / 100	590 ms	8952 KB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
int N, *A;
vector<pii> vec[1000];
void f(int s, int e){
	if(s>e) return;
	int m = s+e>>1;
	vec[m+1].emplace_back(m+1, A[m+1]);
	for(int i=m+2, t=A[m+1]; i<=e; ++i){
		t = Secret(t, A[i]);
		vec[m+1].emplace_back(i, t);
	}
	vec[m].emplace_back(m, A[m]);
	for(int i=m-1, t=A[m]; i>=s; --i){
		t = Secret(A[i], t);
		vec[i].emplace_back(m, t);
	}
	if(e-s<2) return;
	f(s, m), f(m+1, e);
}
int g(int s, int e, int L, int R){
	if(e<L || R<s) return 0;
	int m = s+e>>1;
	if(L<=m && m<R)	return Secret(lower_bound(vec[L].begin(), vec[L].end(), pii(m, 0))->ss, lower_bound(vec[m+1].begin(), vec[m+1].end(), pii(R, 0))->ss);
	return g(s, m, L, R) | g(m+1, e, L, R);
}
void Init(int N_, int A_[]){
	N = N_, A = A_;
	f(0, N-1);
	for(int i=0; i<N; ++i) sort(vec[i].begin(), vec[i].end());
}

int Query(int L, int R){
	if(L==R) return A[L];
	return g(0, N-1, L, R);
}

Compilation message

secret.cpp: In function 'void f(int, int)':
secret.cpp:11:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e>>1;
          ~^~
secret.cpp: In function 'int g(int, int, int, int)':
secret.cpp:27:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e>>1;
          ~^~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	2808 KB	Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2	Correct	147 ms	2444 KB	Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3	Correct	154 ms	2648 KB	Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4	Correct	537 ms	4504 KB	Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5	Runtime error	551 ms	8856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	540 ms	8732 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	564 ms	8864 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	503 ms	8952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	515 ms	8732 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	590 ms	8952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)