oj.uz

Submission #796069

# Submission time Handle Problem Language Result Execution time Memory
796069 2023-07-28T05:44:43 Z Sandarach151 Secret (JOI14_secret) C++17
0 / 100
 370 ms 4328 KB 
#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
 
class SparseTable {
private:
    vector<vector<int>> table;
    vector<int> arr;
    int sze;
    int logSze;
 
    void build(int depth, int left, int right) {
        if (left == right) {
            return;
        } else {
            int mid = (left + right) / 2;
            table[depth][mid] = arr[mid];
            for (int i = mid - 1; i >= left; i--) {
                table[depth][i] = Secret(table[depth][i + 1], arr[i]);
            }
            table[depth][mid + 1] = arr[mid + 1];
            for (int i = mid + 2; i <= right; i++) {
                table[depth][i] = Secret(table[depth][i - 1], arr[i]);
            }
            build(depth + 1, left, mid);
            build(depth + 1, mid + 1, right);
        }
    }
 
    int privQuery(int depth, int queryLeft, int queryRight, int posLeft, int posRight) {
        if (queryLeft > posRight || queryRight <= posLeft) {
            return 0;
        }
        int mid = (posLeft + posRight) / 2;
        if (queryRight == mid) {
            return table[depth][queryLeft];
        } else if (queryLeft == mid + 1) {
            return table[depth][queryRight];
        } else {
            if (queryLeft <= mid && queryRight >= mid + 1) {
                return Secret(table[depth][queryLeft], table[depth][queryRight]);
            } else {
                if (queryLeft >= mid + 1) {
                    return privQuery(depth + 1, queryLeft, queryRight, mid + 1, posRight);
                } else {
                    return privQuery(depth + 1, queryLeft, queryRight, posLeft, mid);
                }
            }
        }
    }
 
public:
    SparseTable(vector<int>& vect) {
        sze = vect.size();
        logSze = ceil(log2(sze)) + 1;
        arr.resize(sze);
        for (int i = 0; i < (int)vect.size(); i++) {
            arr[i] = vect[i];
        }
        table.resize(logSze, vector<int>(sze, 0)); // Initialize the table with 0s
        build(0, 0, sze - 1);
    }
 
    int query(int left, int right) {
        return privQuery(0, left, right, 0, sze - 1);
    }
};
 
SparseTable* temp;
vector<int> array2;
 
void Init(int N, int A[]) {
    vector<int> vect(N);
    array2.resize(vect.size());
    for (int i = 0; i < N; i++) {
        vect[i] = A[i];
        array2[i] = A[i];
    }
    temp = new SparseTable(vect);
}
 
int Query(int L, int R) {
    if (L == R) return array2[L];
    return temp->query(L, R);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 2380 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 98 ms 2340 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 97 ms 2368 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 356 ms 4232 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 353 ms 4328 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 361 ms 4272 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 154975445.
7 Incorrect 370 ms 4300 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 353 ms 4268 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 356 ms 4216 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 360 ms 4300 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.