Submission #162021

#TimeUsernameProblemLanguageResultExecution timeMemory
162021Alexa2001Secret (JOI14_secret)C++17
100 / 100
628 ms8444 KiB
#include "secret.h" #include <bits/stdc++.h> using namespace std; const int Nmax = 1005; int n; int res[Nmax][Nmax], A[Nmax]; void divide(int st, int dr) { if(dr - st <= 3) { if(res[st+1][dr-1] == -1) res[st+1][dr-1] = Secret(A[st+1], A[dr-1]); return; } int mid = (st + dr) / 2; divide(st, mid); divide(mid+1, dr); int i; for(i=mid-1; i>=st; --i) if(res[i][mid] == -1) res[i][mid] = Secret(A[i], res[i+1][mid]); for(i=mid+2; i<=dr; ++i) if(res[mid+1][i] == -1) res[mid+1][i] = Secret(res[mid+1][i-1], A[i]); } void Init(int N, int _A[]) { n = N; int i, j; for(i=0; i<n; ++i) A[i] = _A[i]; for(i=0; i<n; ++i) for(j=i; j<n; ++j) res[i][j] = -1; for(i=0; i<n; ++i) res[i][i] = A[i]; divide(0, n-1); } int answer(int st, int dr, int L, int R) { if(dr - st <= 3) { if(res[L][R] != -1) return res[L][R];/// lungime 4 /// lungime 3 assert(R - L == 2); if(res[L][L+1] != -1) return Secret(res[L][L+1], A[R]); else { assert(res[R-1][R] != -1); return Secret(A[L], res[R-1][R]); } } int mid = (st + dr) / 2; if(L <= mid && mid + 1 <= R) return Secret(res[L][mid], res[mid+1][R]); if(R <= mid) return answer(st, mid, L, R); else return answer(mid+1, dr, L, R); } int Query(int L, int R) { if(L == R) return A[L]; if(L + 1 == R) return Secret(A[L], A[R]); /// lungime minim 3 return answer(0, n-1, L, R); }
#Verdict Execution timeMemoryGrader output
Fetching results...