Submission #1263909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263909		anteknne	비밀 (JOI14_secret)	C++20	100 / 100	354 ms	12388 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 1000 + 17;

int a[MAXN];
int m[4 * MAXN][MAXN];
int n;

void dziel (int p, int k, int i) {
    if (p == k) {
        m[i][p] = a[p];
        return;
    }
    int sr = (p + k)/ 2;
    dziel(p, sr, i * 2);
    dziel(sr + 1, k, i * 2 + 1);
    m[i][sr] = a[sr];
    for (int j = sr - 1; j >= p; j --) {
        m[i][j] = Secret(a[j], m[i][j + 1]);
    }
    if (sr + 1 <= k) {
        m[i][sr + 1] = a[sr + 1];
    }
    for (int j = sr + 2; j <= k; j ++) {
        m[i][j] = Secret(m[i][j - 1], a[j]);
    }
}

void Init(int N, int A[]) {
    n = N;
	for (int i = 0; i < n; i ++) {
        a[i] = A[i];
	}
	dziel(0, n - 1, 1);

}

int wyn = -1;

void odczytaj (int p, int k, int i, int l, int r) {
    if (wyn != -1 || p > r || k < l) {
        return;
    }
    if (p == k) {
        wyn = a[p];
        return;
    }
    int sr = (p + k)/ 2;
    if (l <= sr && r > sr) {
        wyn = Secret(m[i][l], m[i][r]);
        return;
    }
    if (r <= sr) {
        odczytaj(p, sr, i * 2, l, r);
    } else {
        odczytaj(sr + 1, k, i * 2 + 1, l, r);
    }
}

int Query(int l, int r) {
    wyn = -1;
    //cout << 0 << " " << n - 1 << "\n";
    odczytaj(0, n - 1, 1, l, r);

	return wyn;
}

• Subtask 1: 100 / 100