제출 #1277074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277074		nanaseyuzuki	비밀 (JOI14_secret)	C++20	100 / 100	344 ms	4692 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 1e3 + 5, inf = 1e9;

int n, a[mn];

// int Secret(int a, int b){

// }

struct Node{ 
    vector <int> prefix, suffix;

    Node operator+(const Node& other) const{
        Node res;
        int n1 = prefix.size(), n2 = other.prefix.size();
        res.prefix.resize(n1 + n2);
        res.suffix.resize(n1 + n2);

        for(int i = 0; i < n1; i++) res.prefix[i] = prefix[i];
        for(int i = 0; i < n2; i++) res.prefix[n1 + i] = Secret(prefix.back(), other.prefix[i]);

        res.suffix[0] = res.prefix[n1 + n2 - 1];
        for(int i = 0; i < n2; i++) res.suffix[n1 + i] = other.suffix[i];
        for(int i = n1 - 1; i >= 1; i--) res.suffix[i] = Secret(suffix[i], other.suffix[0]);

        return res;
    }


} st[mn << 2];

void build(int id, int l, int r){
    if(l == r){
        st[id].prefix.push_back(a[l]);
        st[id].suffix.push_back(a[r]);
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    if(id != 1) st[id] = st[id << 1] + st[id << 1 | 1];
}

int get(int id, int l, int r, int u, int v){
    if(l == r) return a[l];
    int mid = (l + r) >> 1;
    if(v <= mid) return get(id << 1, l, mid, u, v);
    else if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
    return Secret(st[id << 1].suffix[u - l], st[id << 1 | 1].prefix[v - mid - 1]);
}

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

int Query(int L, int R){
    L ++, R ++;
    return get(1, 1, n, L, R);
}

• Subtask 1: 100 / 100