Submission #1273710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273710		lamlamlam	Secret (JOI14_secret)	C++20	100 / 100	341 ms	4668 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int MN = 1005;
int n,a[MN];
struct Segtree{
    struct Node{
        vector<int> pre, suf;
        Node(int n){
            pre.push_back(n);
            suf.push_back(n);
        }
        Node(){}
        Node operator + (const Node &o) const{
            Node res;
            for(auto x:pre) res.pre.push_back(x);
            for(auto x:o.pre) res.pre.push_back(Secret(pre.back(),x));
            res.suf.push_back(res.pre.back());
            for(auto x:suf) if(x!=suf[0]) res.suf.push_back(Secret(x,o.suf[0]));
            for(auto x:o.suf) res.suf.push_back(x);
            return res;
        }
    } st[MN*4];
    void init(int u,int l,int r){
        if(l>r) return;
        if(l==r) {
            st[u] = Node(a[l]);
            return;
        }
        int mid = (l+r)/2;
        init(u*2,l,mid);
        init(u*2+1,mid+1,r);
        if(u!=1) st[u] = st[u*2] + st[u*2+1];
    }
    int query(int u,int l,int r,int x,int y){
        if(l==r) return a[l];
        int mid = (l+r)/2;
        if(y<=mid) return query(u*2,l,mid,x,y);
        else if(x>mid) return query(u*2+1,mid+1,r,x,y);
        // y>=mid+1 and x<=mid;
//        cerr << "GETTING:: " << u << ' ' << l << ' ' << r << ' ' << x << ' ' << y << endl;
        return Secret(st[u*2].suf[x-l],st[u*2+1].pre[y-mid-1]);
    }
}st;
void Init(int N, int A[]) {
    n = N;
    for(int i=0; i<N; i++) a[i+1] = A[i];
    st.init(1,1,N);
//    cerr << "?????????????\n";
}
int Query(int L, int R) {
    return st.query(1,1,n,L+1,R+1);
}

• Subtask 1: 100 / 100