oj.uz

답안 #795998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
795998 2023-07-28T03:55:09 Z Sandarach151 비밀 (JOI14_secret) C++17
0 / 100
 355 ms 8700 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(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

# 결과 실행 시간 메모리 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