oj.uz

답안 #109195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109195 2019-05-05T12:10:41 Z maruii 비밀 (JOI14_secret) C++14
0 / 100
 590 ms 8952 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){
	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

# 결과 실행 시간 메모리 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)