Submission #113075

#	Time	Username	Problem	Language	Result	Execution time	Memory
113075		Alex18mai	Secret (JOI14_secret)	C++17	100 / 100	504 ms	12388 KiB

secret

#include "secret.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int v[1010];
int arb[4010][1010]; // nod , pos
int n;

void prop (int nod , int st , int dr){
    if (st == dr){
        arb[nod][st] = v[st];
        return;
    }

    int mij = st + dr;
    mij /= 2;

    prop (nod * 2 , st , mij);
    prop (nod * 2 + 1 , mij + 1 , dr);

    arb[nod][mij] = v[mij];
    arb[nod][mij+1] = v[mij+1];

    for (int i=mij+2; i<=dr; i++){
        arb[nod][i] = Secret (arb[nod][i-1] , v[i]);
    }
    for (int i=mij-1; i>=st; i--){
        arb[nod][i] = Secret (v[i] , arb[nod][i+1]);
    }
}


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

int query (int nod , int st , int dr , int MIN , int MAX){
    int mij = st + dr;
    mij /= 2;
    if (MIN <= mij && MAX >= mij){
        //cout<<MIN<<" "<<MAX<<" "<<mij<<'\n';
        int ret = arb[nod][MIN];
        if (MAX > mij){
            ret = Secret (ret , arb[nod][MAX]);
        }
        return ret;
    }
    if (MAX < mij){
        return query (nod * 2 , st , mij , MIN , MAX);
    }
    else{
        return query (nod * 2 + 1 , mij + 1 , dr , MIN , MAX);
    }
}

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

• Subtask 1: 100 / 100