#include <bits/stdc++.h>
#include <secret.h>
using namespace std;
using ll = long long;
//#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//void setupIO(){
// #define name "Whisper"
// //Phu Trong from Nguyen Tat Thanh High School for gifted student
// srand(time(NULL));
// cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// cout << fixed << setprecision(10);
//}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
vector<int> a;
int nArr;
vector<vector<int>> sum;
//int Secret(int lx, int rx){
// return (lx + rx);
//}
void dnc(int l, int r){
if (l == r){
sum[l][l] = a[l];
return;
}
if (l > r) return;
int mid = (l + r) >> 1;
sum[mid][mid] = a[mid];
sum[mid + 1][mid + 1] = a[mid + 1];
for (int i = mid - 1; i >= l; --i)
sum[i][mid] = Secret(a[i], sum[i + 1][mid]);
for (int i = mid + 2; i <= r; ++i)
sum[mid + 1][i] = Secret(sum[mid + 1][i - 1], a[i]);
dnc(l, mid - 1);
dnc(mid + 1, r);
}
void Init(int N, int A[]){
a.resize(N);
sum.resize(N, vector<int>(N));
nArr = N;
for (int i = 0; i < N; ++i) a[i] = A[i];
dnc(0, nArr - 1);
}
int Get(int l, int r, int u, int v){
int mid = (l + r) >> 1;
if (u <= mid && mid < v) return Secret(sum[u][mid], sum[mid + 1][v]);
if (v <= mid)
return Get(l, mid - 1, u, v);
return Get(mid + 1, r, u, v);
}
int Query(int l, int r){
return (l == r ? a[l] : Get(0, nArr - 1, l, r));
}
//void Whisper(){
// int a[8] = {1, 4, 7, 2, 5, 8, 3, 6};
// Init(8, a);
// cout << "CASE 1: " << Query(0, 3) << '\n';
// cout << "CASE 2: " << Query(1, 7) << '\n';
// cout << "CASE 3: " << Query(5, 5) << '\n';
// cout << "CASE 4: " << Query(2, 4) << '\n';
//}
//
//
//signed main(){
// setupIO();
// int Test = 1;
//// cin >> Test;
// for ( int i = 1 ; i <= Test ; i++ ){
// Whisper();
// if (i < Test) cout << '\n';
// }
//}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
102 ms |
3752 KB |
Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
104 ms |
3664 KB |
Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
104 ms |
3788 KB |
Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
385 ms |
8368 KB |
Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
362 ms |
8276 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
372 ms |
8348 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
364 ms |
8148 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
369 ms |
8532 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
373 ms |
8276 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
371 ms |
8536 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
