Submission #25315

#	Time	Username	Problem	Language	Result	Execution time	Memory
25315		kajebiii	Secret (JOI14_secret)	C++14	6 / 100	659 ms	6192 KiB

secret

#include "secret.h"
#include <vector>
#include <stdio.h>

using namespace std;

const int MAX_N = 1e3 + 100;
const int ROOT_N = 32;

struct IDX
{
    int P; vector<int> val;
    vector<vector<int> > logR, logL;
    IDX() {}
    IDX(int n, int nr[]) {
        for(P=1; P<n; P<<=1);
        val = vector<int>(2*P, 0);
        for(int i=0; i<n; i++) val[P+i] = nr[i];
        for(int i=P-1; i>=1; i--)
            val[i] = Secret(val[i*2], val[i*2+1]);
        logL = logR = vector<vector<int> >(n, vector<int>());
        for(int i=0; i<n; i++) {
            logR[i].push_back(nr[i]);
            int v = i+P;
            while(v & (v-1)) {
                if(v % 2 == 1)
                    logR[i].push_back(Secret(val[v-1], logR[i].back()));
                else
                    logR[i].push_back(Secret(val[v/2-1], logR[i].back()));
                v--;
                v>>=1;
            }
            logL[i].push_back(nr[i]);
            v = i+P;
            while(v & (v+1)) {
                if(v % 2 == 0)
                    logL[i].push_back(Secret(logL[i].back(), val[v+1]));
                else
                    logL[i].push_back(Secret(logL[i].back(), val[v/2+1]));
                v++;
                v>>=1;
            }
        }
    }
    int getQ(int a, int b) {
        int l = a, r = b;
        a += P, b += P;
        int la = -1, lb = -1, cnt = 0;
        while(a <= b) {
            if(a%2 == 1) la = cnt, a++;
            if(b%2 == 0) lb = cnt, b--;
            a >>= 1; b >>= 1; cnt++;
        }
//        printf("[%d %d] [%d %d]\n", l, r, la, lb);
        if(la == -1) return logR[r][lb];
        if(lb == -1) return logL[l][la];
//        printf("Sp [%d %d]\n", logL[l][la], logR[r][lb]);
        return Secret(logL[l][la], logR[r][lb]);
    }
};
IDX idx;
void Init(int N, int A[]) {
    idx = IDX(N, A);
}

int Query(int L, int R) {
    return idx.getQ(L, R);
}

• Subtask 1: 6 / 100