#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
//=================================
const int MAX = 1005;
int arr[MAX], res[MAX][MAX], n;
int secret(int a, int b){ return a+b/2*2; }
void solve(int l, int r){
if (l == r) return;
int m = l+(r-l)/2;
res[m][m] = arr[m], res[m+1][m+1] = arr[m+1];
for (int i = m-1; i >= l; i--) res[i][m] = Secret(arr[i], res[i+1][m]);
for (int i = m+2; i <= r; i++) res[m+1][i] = Secret(res[m+1][i-1], arr[i]);
solve(l, m); solve(m+1, r);
}
int solve(int l, int r, int tl, int tr){
int m = l+(r-l)/2;
if (tl <= m && m < tr) return Secret(res[tl][m], res[m+1][tr]);
return (tr <= m? solve(l, m, tl, tr) : solve(m+1, r, tl, tr));
}
void Init(int N, int v[]){
n = N;
for (int i = 0; i < n; i++) arr[i] = v[i];
solve(0, n-1);
}
int Query(int l, int r){
if (l == r) return arr[l];
return solve(0, n-1, l, r);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
121 ms |
4316 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
2 |
Correct |
126 ms |
4336 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
3 |
Correct |
123 ms |
4300 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
4 |
Correct |
438 ms |
8140 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
5 |
Correct |
433 ms |
8140 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
6 |
Correct |
438 ms |
8220 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
7 |
Correct |
463 ms |
8224 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
8 |
Correct |
431 ms |
8136 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
9 |
Correct |
432 ms |
8224 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
10 |
Correct |
432 ms |
8204 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |