Submission #795998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
795998	2023-07-28T03:55:09 Z	Sandarach151	Secret (JOI14_secret)	C++17	0 / 100	355 ms	8700 KB

secret

#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(depth==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));
            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	Runtime error	96 ms	4684 KB	Execution killed with signal 11
2	Runtime error	96 ms	4684 KB	Execution killed with signal 11
3	Runtime error	95 ms	4680 KB	Execution killed with signal 11
4	Runtime error	353 ms	8596 KB	Execution killed with signal 11
5	Runtime error	353 ms	8620 KB	Execution killed with signal 11
6	Runtime error	352 ms	8576 KB	Execution killed with signal 11
7	Runtime error	353 ms	8620 KB	Execution killed with signal 11
8	Runtime error	354 ms	8700 KB	Execution killed with signal 11
9	Runtime error	353 ms	8672 KB	Execution killed with signal 11
10	Runtime error	355 ms	8652 KB	Execution killed with signal 11