#include "secret.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX_N 1000
vector<int> v;
int n;
int dp[MAX_N+1][MAX_N+1];
void init(int x, int y){
if(x==y) {
dp[x][y] = v[x];
return;
}
if(x==y-1){
dp[x][y] = Secret(v[x], v[y]);
return;
}
int m = (x+y)/2;
dp[m][m] = v[m];
dp[m+1][m+1] = v[m+1];
for(int i=m-1; i>=x; i--) dp[i][m] = Secret(v[i], dp[i+1][m]);
for(int j=m+2; j<=y; j++) dp[m+1][j] = Secret(dp[m+1][j-1], v[j]);
init(x, m);
init(m+1, y);
}
void Init(int N, int A[]) {n = N;
for(int i=0; i<N; i++){
v.push_back(A[i]);
}
init(0, N-1);
}
int Query(int L, int R) {
if(L==R){
return v[L];
}
if(L==R-1){
return Secret(v[L], v[R]);
}
int s = 0, e = n-1, m;
while(1){
m = (s+e)/2;
if(L<=m && R>m){
return Secret(dp[L][m], dp[m+1][R]);
}
if(R<=m){
e = m;
}else{
s = m+1;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
4472 KB |
Output is correct - number of calls to Secret by Init = 3833, maximum number of calls to Secret by Query = 1 |
2 |
Correct |
137 ms |
4344 KB |
Output is correct - number of calls to Secret by Init = 3842, maximum number of calls to Secret by Query = 1 |
3 |
Correct |
137 ms |
4536 KB |
Output is correct - number of calls to Secret by Init = 3851, maximum number of calls to Secret by Query = 1 |
4 |
Incorrect |
476 ms |
8368 KB |
Output isn't correct - number of calls to Secret by Init = 8456, maximum number of calls to Secret by Query = 1 |
5 |
Incorrect |
480 ms |
8204 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
6 |
Incorrect |
486 ms |
8244 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
7 |
Incorrect |
486 ms |
8212 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
8 |
Incorrect |
489 ms |
8440 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
9 |
Incorrect |
481 ms |
8316 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
10 |
Incorrect |
485 ms |
8288 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |