제출 #68562

#제출 시각아이디문제언어결과실행 시간메모리
68562evpipisSecret (JOI14_secret)C++11
100 / 100
673 ms12608 KiB
#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 timeMemoryGrader output
Fetching results...