# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
29730 |
2017-07-20T11:43:24 Z |
cdemirer |
Secret (JOI14_secret) |
C++14 |
|
626 ms |
9920 KB |
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int _N;
int _A[1000];
int hesaplar[1000][1000];
void calc(int l, int r) {
if (l == r) {
return;
}
int mid = (l+r)/2;
if (r - l == 1) {
hesaplar[mid][mid+1] = Secret(_A[mid], _A[mid+1]);
hesaplar[mid+1][mid] = _A[mid];
return;
}
calc(l, mid-1);
calc(mid+1, r);
int lmid = (l+mid)/2, rmid = (mid+1+r)/2;
if (mid-1 > lmid) hesaplar[mid][mid-1] = _A[mid-1];
for (int i = mid-2; i > lmid; i--) {
hesaplar[mid][i] = Secret(_A[i], hesaplar[mid][i+1]);
}
if (lmid == mid-1) {
hesaplar[mid][lmid] = _A[lmid];
}
else {
hesaplar[mid][lmid] = Secret(_A[lmid], hesaplar[mid][lmid+1]);
}
for (int i = lmid-1; i >= l; i--) {
//cerr << "A" << endl;
//cerr << "lmid, i, mid, lmid+1 : " << lmid << " " << i << " " << mid << " " << mid+1 << endl;
hesaplar[mid][i] = Secret(hesaplar[lmid][i], hesaplar[mid][lmid]);
//cerr << "B" << endl;
}
for (int i = mid+1; i < rmid; i++) {
hesaplar[mid][i] = Secret(hesaplar[mid][i-1], _A[i]);
}
for (int i = rmid; i <= r; i++) {
hesaplar[mid][i] = Secret(hesaplar[mid][rmid-1], hesaplar[rmid][i]);
}
}
void Init(int N, int A[]) {
memset(hesaplar, -1, sizeof(hesaplar));
_N = N;
for (int i = 0; i < N; i++) _A[i] = A[i];
for (int i = 0; i < N; i++) hesaplar[i][i] = _A[i];
calc(0, _N-1);
}
int Query(int L, int R) {
int l = 0, r = _N-1;
while (true) {
//cerr << l << " " << r << " : " << L << " " << R << endl;
int mid = (l+r)/2;
if (L == R && L == mid) return _A[mid];
else if (L <= mid && R >= mid) {
int a = hesaplar[mid][L];
int b = hesaplar[mid][R];
return Secret(a, b);
}
else if (R == mid) {
return Secret(hesaplar[mid][L], _A[mid]);
}
else if (R == mid-1) {
return hesaplar[mid][L];
}
else if (L == mid) {
return hesaplar[mid][R];
}
else if (R < mid) {
r = mid;
}
else if (L > mid) {
l = mid+1;
}
else {
cerr << "Impossible branch" << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
153 ms |
9920 KB |
Wrong Answer: Query(255, 409) - expected : 307522235, actual : 38999632. |
2 |
Incorrect |
153 ms |
9920 KB |
Wrong Answer: Query(127, 153) - expected : 342921603, actual : 542288066. |
3 |
Incorrect |
173 ms |
9920 KB |
Wrong Answer [1] |
4 |
Incorrect |
596 ms |
9920 KB |
Wrong Answer [1] |
5 |
Incorrect |
619 ms |
9920 KB |
Wrong Answer [1] |
6 |
Incorrect |
626 ms |
9920 KB |
Wrong Answer [1] |
7 |
Incorrect |
609 ms |
9920 KB |
Wrong Answer [1] |
8 |
Incorrect |
576 ms |
9920 KB |
Wrong Answer [1] |
9 |
Incorrect |
599 ms |
9920 KB |
Wrong Answer [1] |
10 |
Incorrect |
589 ms |
9920 KB |
Wrong Answer [1] |