oj.uz

Submission #25315

# Submission time Handle Problem Language Result Execution time Memory
25315 2017-06-21T06:42:29 Z kajebiii Secret (JOI14_secret) C++14
6 / 100
 659 ms 6192 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 6060 KB Output is correct - number of calls to Secret by Init = 7692, maximum number of calls to Secret by Query = 1
2 Correct 183 ms 6060 KB Output is correct - number of calls to Secret by Init = 7701, maximum number of calls to Secret by Query = 1
3 Incorrect 183 ms 6060 KB Output isn't correct - number of calls to Secret by Init = 9245, maximum number of calls to Secret by Query = 1
4 Incorrect 659 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17131, maximum number of calls to Secret by Query = 1
5 Incorrect 656 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1
6 Incorrect 636 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1
7 Incorrect 633 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1
8 Incorrect 639 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1
9 Incorrect 609 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1
10 Incorrect 616 ms 6192 KB Output isn't correct - number of calls to Secret by Init = 17144, maximum number of calls to Secret by Query = 1