oj.uz

답안 #109194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109194 2019-05-05T12:09:08 Z maruii 비밀 (JOI14_secret) C++14
100 / 100
 572 ms 4708 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[1001];
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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 2500 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 172 ms 2552 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 2632 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 572 ms 4544 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 552 ms 4568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 562 ms 4708 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 556 ms 4648 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 559 ms 4628 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 558 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 560 ms 4532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1