Submission #1085990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085990		Icelast	Secret (JOI14_secret)	C++17	100 / 100	310 ms	4516 KiB

secret

#include "secret.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct MeowTree{
    struct Info{
        int v = 0;
    };
    struct Node{
        vector<int> lt, rt;
        int mid;
    };
    int n, N;
    vector<Node> T;
    MeowTree(int n, vector<int> a) : n(n){
        N = 1;
        while(N < n){
            N*=2;
        }
        T.resize(N*2);
        auto build = [&](auto build, int node, int low, int high) -> void{
            int mid = (low+high)/2;
            T[node].mid = mid;
            if(low == high){
                T[node].lt.push_back(a[mid]);
                return;
            }
            T[node].lt.push_back(a[mid]);
            T[node].rt.push_back(a[mid+1]);
            for(int i = mid-1; i >= low; i--){
                if(i >= n) continue;
                T[node].lt.push_back(Secret(a[i], T[node].lt.back()));
            }
            for(int i = mid+2; i <= min(n, high); i++){
                T[node].rt.push_back(Secret(T[node].rt.back(), a[i]));
            }
            build(build, node*2, low, mid);
            build(build, node*2+1, mid+1, high);
        };
        build(build, 1, 1, N);
    }
    int query(int l, int r){
        if(l == r) return T[l+N-1].lt[0];
        int low = l+N-1, high = r+N-1;
        while(low != high){
            if(low > high) swap(low, high);
            high/=2;
        }
        int node = low, mid = T[node].mid;
        return Secret(T[node].lt[mid-l], T[node].rt[r-mid-1]);
    }
};
MeowTree T(1, {1});
void Init(int n, int A[]) {
    vector<int> a(n+1);
    for(int i = 0; i < n; i++){
        a[i+1] = A[i];
    }
    T = MeowTree(n, a);
}
int Query(int l, int r) {
    l++;
    r++;
    return T.query(l, r);
}

• Subtask 1: 100 / 100