제출 #1269145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269145		uranium235	비밀 (JOI14_secret)	C++17	0 / 100	343 ms	4508 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dnc(11, vector<int>(1000));
vector<vector<int>> cnd(11, vector<int>(1000));

void divide(int l, int r, int v, int *a, int side) {
    if (l == r) dnc[v][l] = cnd[v][l] = a[l];
    else {
        int m = (l + r) / 2;
        divide(l, m, v + 1, a, side == -1 ? -1 : 0);
        divide(m + 1, r, v + 1, a, side == 1 ? 1 : 0);
        if (side != -1) {
            for (int i = l; i <= m; i++) dnc[v][i] = dnc[v + 1][i];
            for (int i = m + 1; i <= r; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
        }
        if (side != 1) {
            for (int i = r; i > m; i--) cnd[v][i] = cnd[v + 1][i];
            for (int i = m; i >= l; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
        }
    }
}

int nn, edgecase;
int conquer(int ll, int rr, int l, int r, int v) {
    // cout << "dividng " << l << " " << r << endl;
    if (l == r) return dnc[max(0, v - 1)][l];

    int m = (l + r) / 2;
    if (rr <= m) return conquer(ll, rr, l, m, v + 1);
    else if (ll > m) return conquer(ll, rr, m + 1, r, v + 1);
    
    return Secret(cnd[v][ll], dnc[v][rr]);
}

void Init(int n, int a[]) {
    nn = n;
    if (n == 1) {
        edgecase = a[0];
        return;
    }
    int m = (n - 1) / 2;
    divide(0, m, 0, a, -1);
    divide(m + 1, n - 1, 0, a, 1);
    cout << endl;
}

int Query(int l, int r) {
    if (nn == 1) return edgecase;
    // cout << "query" << endl;
    return conquer(l, r, 0, nn - 1, 0);
}

• Subtask 1: 0 / 100