oj.uz

Submission #113075

# Submission time Handle Problem Language Result Execution time Memory
113075 2019-05-23T13:56:11 Z Alex18mai Secret (JOI14_secret) C++17
100 / 100
 504 ms 12388 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 6460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 6648 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 6484 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 496 ms 12276 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 497 ms 12340 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 495 ms 12292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 502 ms 12280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 502 ms 12292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 504 ms 12388 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 501 ms 12340 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1