oj.uz

Submission #25316

# Submission time Handle Problem Language Result Execution time Memory
25316 2017-06-21T06:43:51 Z kajebiii Secret (JOI14_secret) C++14
0 / 100
 636 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(val[v/2]);
                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(val[v/2]);
                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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 6060 KB Wrong Answer: Query(113, 206) - expected : 536899947, actual : 806775907.
2 Incorrect 169 ms 6060 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 459311273.
3 Incorrect 159 ms 6060 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 69300276.
4 Incorrect 586 ms 6192 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 294879402.
5 Incorrect 636 ms 6192 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 911755284.
6 Incorrect 599 ms 6192 KB Wrong Answer: Query(888, 892) - expected : 825894562, actual : 11642723.
7 Incorrect 579 ms 6192 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 591439875.
8 Incorrect 619 ms 6192 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 492998984.
9 Incorrect 626 ms 6192 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 948179206.
10 Incorrect 599 ms 6192 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 876162437.