Submission #795998

#TimeUsernameProblemLanguageResultExecution timeMemory
795998Sandarach151Secret (JOI14_secret)C++17
0 / 100
355 ms8700 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...