# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
68562 | evpipis | Secret (JOI14_secret) | C++11 | 673 ms | 12608 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "secret.h"
//#define TEST
#ifdef TEST
#define MAX_N 1000
#define MAX_Q 10000
#define MAX_VALUE 1000000000
static int N;
static int A[MAX_N];
static int Q;
static int L[MAX_Q];
static int R[MAX_Q];
static int secret_count;
int Secret(int X, int Y) {
++secret_count;
if (!(0 <= X && X <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
if (!(0 <= Y && Y <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
}
#endif
const int len = 1005;
int arr[len], val[4*len][len], n;
void build(int p, int l, int r){
int mid = (l+r)/2;
val[p][mid] = arr[mid];
if (l != r) val[p][mid+1] = arr[mid+1];
for (int i = mid-1; i >= l; i--)
val[p][i] = Secret(arr[i], val[p][i+1]);
for (int i = mid+2; i <= r; i++)
val[p][i] = Secret(val[p][i-1], arr[i]);
if (l != r)
build(2*p, l, mid), build(2*p+1, mid+1, r);
}
int query(int p, int l, int r, int i, int j){
if (l == r)
return arr[l];
int mid = (l+r)/2;
if (j <= mid)
return query(2*p, l, mid, i, j);
else if (i > mid)
return query(2*p+1, mid+1, r, i, j);
return Secret(val[p][i], val[p][j]);
}
void Init(int N, int A[]) {
n = N;
for (int i = 0; i < n; i++)
arr[i] = A[i];
build(1, 0, n-1);
Secret(0, 1000000000);
}
int Query(int l, int r) {
return query(1, 0, n-1, l, r);
}
#ifdef TEST
int main() {
freopen("input.txt", "r", stdin);
int i, j;
int secret_count_by_init;
int max_secret_count_by_query = 0;
if (1 != scanf("%d", &N)) {
fprintf(stderr, "error: cannot read N.\n");
exit(1);
}
if (!(1 <= N && N <= MAX_N)) {
fprintf(stderr, "error: N is out of bounds.\n");
exit(1);
}
for (i = 0; i < N; ++i) {
if (1 != scanf("%d", &A[i])) {
fprintf(stderr, "error: cannot read A[%d].\n", i);
exit(1);
}
if (!(0 <= A[i] && A[i] <= MAX_VALUE)) {
fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
exit(1);
}
}
if (1 != scanf("%d", &Q)) {
fprintf(stderr, "error: cannot read Q.\n");
exit(1);
}
if (!(0 <= Q && Q <= MAX_Q)) {
fprintf(stderr, "error: Q is out of bounds.\n");
exit(1);
}
for (j = 0; j < Q; ++j) {
if (2 != scanf("%d%d", &L[j], &R[j])) {
fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
exit(1);
}
if (!(0 <= L[j] && L[j] <= R[j] && R[j] <= N - 1)) {
fprintf(stderr,
"error: L[%d] and R[%d] do not satisfy the constraints.\n",
j, j);
exit(1);
}
}
secret_count = 0;
Init(N, A);
secret_count_by_init = secret_count;
for (j = 0; j < Q; ++j) {
secret_count = 0;
printf("%d\n", Query(L[j], R[j]));
if (max_secret_count_by_query < secret_count) {
max_secret_count_by_query = secret_count;
}
}
fprintf(stderr, "number of calls to Secret by Init : %d\n",
secret_count_by_init);
fprintf(stderr, "maximum number of calls to Secret by Query : %d\n",
max_secret_count_by_query);
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |