oj.uz

Submission #109193

# Submission time Handle Problem Language Result Execution time Memory
109193 2019-05-05T12:08:39 Z maruii Secret (JOI14_secret) C++14
0 / 100
 586 ms 8968 KB 
#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){
	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:10:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e>>1;
          ~^~
secret.cpp: In function 'int g(int, int, int, int)':
secret.cpp:26: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 158 ms 2424 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 188 ms 2524 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 167 ms 2540 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 570 ms 4584 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Runtime error 501 ms 8948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 586 ms 8968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 550 ms 8924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 524 ms 8852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 552 ms 8884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 536 ms 8796 KB Execution killed with signal 11 (could be triggered by violating memory limits)