#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
// #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];
using vi = vector<int>;
using vvi = vector<vi>;
//static int secret_count;
int n = 1005;
vvi lef(n,vi(n)),rig(n,vi(n));
vi a;
// 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;
// }
void build(int l,int r)
{
if (l == r){lef[l][l] = rig[l][l] = a[l];return;}
if (l == r - 1){lef[l][l] = a[l];rig[l + 1][l] = a[l];return;}
int mid = (l + r)/2;
lef[mid][mid] = a[mid];
rig[mid + 1][mid] = a[mid + 1];
for (int i = mid - 1;i>=l;i--)lef[i][mid] = Secret(a[i],lef[i + 1][mid]);
for (int i = mid + 2;i<=r + 1;i++)rig[i][mid] = Secret(rig[i - 1][mid],a[i]);
build(l,mid - 1);
build(mid + 1,r);
}
void Init(int N, int A[]) {
n = N;
a.resize(n + 1);
for (int i = 1;i<=N;i++)a[i] = A[i - 1];
build(1,n);
}
int Query(int L, int R,int l,int r) {
if (L == R)return a[L];
if (L == R - 1)return Secret(a[L],a[L + 1]);
int mid = (l + r)/2;
if (L <= mid && mid + 1 <= R){
assert(lef[L][mid] != -1 && rig[R][mid] != -1);
return Secret(lef[L][mid],rig[R][mid]);
}
if (R <= mid)return Query(L,R,l,mid - 1);
return Query(L,R,mid + 1,r);
}
int Query(int L,int R)
{
return Query(L + 1,R + 1,1,n);
}
// int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// //cout<<Secret(Secret(1,4),Secret(7,2))<<endl;
// 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;
// cout<<Query(L[j],R[j])<<endl;
// 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;
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
146 ms |
10308 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
150 ms |
10308 KB |
Output is correct - number of calls to Secret by Init = 3594, maximum number of calls to Secret by Query = 1 |
| 3 |
Incorrect |
147 ms |
10276 KB |
Wrong Answer: Query(254, 256) - expected : 551536758, actual : 495989008. |
| 4 |
Correct |
533 ms |
12256 KB |
Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
519 ms |
12300 KB |
Output is correct - number of calls to Secret by Init = 7964, maximum number of calls to Secret by Query = 1 |
| 6 |
Incorrect |
503 ms |
12248 KB |
Wrong Answer: Query(781, 783) - expected : 150199089, actual : 554944275. |
| 7 |
Correct |
512 ms |
12332 KB |
Output is correct - number of calls to Secret by Init = 7964, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
520 ms |
12172 KB |
Output is correct - number of calls to Secret by Init = 7964, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
528 ms |
12208 KB |
Output is correct - number of calls to Secret by Init = 7964, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
513 ms |
12228 KB |
Output is correct - number of calls to Secret by Init = 7964, maximum number of calls to Secret by Query = 1 |
