oj.uz

답안 #109191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109191 2019-05-05T11:56:21 Z maruii 비밀 (JOI14_secret) C++14
0 / 100
 575 ms 9076 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(s==e) 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());
	Secret(0, 1000000000);
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 2492 KB Output is correct - number of calls to Secret by Init = 3579, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 2552 KB Output is correct - number of calls to Secret by Init = 3587, maximum number of calls to Secret by Query = 1
3 Correct 154 ms 2632 KB Output is correct - number of calls to Secret by Init = 3596, maximum number of calls to Secret by Query = 1
4 Correct 553 ms 4728 KB Output is correct - number of calls to Secret by Init = 7970, maximum number of calls to Secret by Query = 1
5 Runtime error 508 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 524 ms 9076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 575 ms 8944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 514 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 560 ms 8964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 568 ms 9000 KB Execution killed with signal 11 (could be triggered by violating memory limits)