# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
85566 | KCSC | 비밀 (JOI14_secret) | C++14 | 649 ms | 6336 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int Secret(int x, int y);
void Init(int n, int arr[]);
int Query(int le, int ri);
/*
int Secret(int x, int y) {
return x xor y xor 13; }
*/
map<pair<int, int>, int> mmp;
int secret(int x, int y) {
if (mmp.find(make_pair(x, y)) == mmp.end()) {
mmp[make_pair(x, y)] = Secret(x, y); }
return mmp[make_pair(x, y)]; }
const int DIM = 1005;
vector<int> lef[DIM * 4], rig[DIM * 4];
void build(int nd, int le, int ri, int arr[]) {
if (le != ri) {
int md = (le + ri) / 2;
build(nd * 2, le, md, arr);
build(nd * 2 + 1, md + 1, ri, arr); }
lef[nd].resize(ri - le + 1); lef[nd][0] = arr[le];
rig[nd].resize(ri - le + 1); rig[nd][ri - le] = arr[ri];
if (le != ri and nd != 1) {
int md = (le + ri) / 2;
for (int i = 1; i <= ri - le; ++i) {
lef[nd][i] = secret(lef[nd][i - 1], arr[le + i]); }
for (int i = ri - le - 1; i >= 0; --i) {
rig[nd][i] = secret(arr[le + i], rig[nd][i + 1]); } } }
int query(int nd, int le, int ri, int st, int en) {
if (le == ri) {
return lef[nd][0]; }
else {
int md = (le + ri) / 2;
if (en <= md) {
return query(nd * 2, le, md, st, en); }
if (md < st) {
return query(nd * 2 + 1, md + 1, ri, st, en); }
return secret(rig[nd * 2][st - le], lef[nd * 2 + 1][en - (md + 1)]); } }
int _n;
void Init(int n, int arr[]) {
build(1, 0, n - 1, arr); _n = n; }
int Query(int le, int ri) {
return query(1, 0, _n - 1, le, ri); }
/*
int arr[10];
int main(void) {
#ifdef HOME
freopen("secret.in", "r", stdin);
freopen("secret.out", "w", stdout);
#endif
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i]; }
Init(n, arr);
int m; cin >> m;
while (m--) {
int le, ri; cin >> le >> ri;
int val = arr[le];
for (int i = le + 1; i <= ri; ++i) {
val = Secret(val, arr[i]); }
cout << Query(le, ri) << " " << val << "\n"; }
return 0; }
*/
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |