Submission #1087964

#TimeUsernameProblemLanguageResultExecution timeMemory
10879644QT0RSecret (JOI14_secret)C++17
100 / 100
331 ms5712 KiB
#include <bits/stdc++.h> #include "secret.h" using namespace std; map<pair<int,int>,int> mp; int mySecret(int X, int Y){ if (!mp.count({X,Y}))mp[{X,Y}]=Secret(X,Y); return mp[{X,Y}]; } vector<int> lft[1003]; vector<int> rght[1003]; int wej[1003]; int n; void build(int l, int p){ if (l==p)return; int md=(l+p)/2; lft[md].push_back(wej[md]); for (int i = md-1; i>=l; i--){ lft[md].push_back(mySecret(wej[i],lft[md].back())); } rght[md+1].push_back(wej[md+1]); for (int i = md+2; i<=p; i++){ rght[md+1].push_back(mySecret(rght[md+1].back(),wej[i])); } build(l,md); build(md+1,p); } void Init(int N, int A[]){ for (int i = 0; i<N; i++)wej[i]=A[i]; n=N; build(0,N-1); } int find(int l, int p){ int a=0,b=n-1,md=(a+b)/2; while(l>md || p<=md){ if (l>md)a=md+1; else b=md; md=(a+b)/2; } return md; } int Query(int l, int p){ if (l==p)return wej[l]; int mid=find(l,p); return mySecret(lft[mid][mid-l],rght[mid+1][p-mid-1]); }
#Verdict Execution timeMemoryGrader output
Fetching results...