# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
365163 | Bill_00 | Secret (JOI14_secret) | C++14 | 511 ms | 8528 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int ans[1001][1001];
void build(int l,int r,int height){
if(l>r){
return;
}
if(l==r){
ans[l][r]=a[l];
return;
}
if(height==9){
int m=l+r>>1;
ans[m][m]=a[m];
ans[m+1][m+1]=a[m+1];
if(m-l==3){
ans[l][l+1]=Secret(a[l],a[l+1]);
ans[l+2][l+3]=Secret(a[l+2],a[l+3]);
ans[l][l+3]=Secret(ans[l][l+1],ans[l+2][l+3]);
ans[l+1][l+3]=Secret(a[l+1],ans[l+2][l+3]);
}
else{
int k=a[m];
for(int i=m-1;i>=l;i--){
k=Secret(a[i],k);
ans[i][m]=k;
}
}
if(r-m-1==3){
ans[r-1][r]=Secret(a[r-1],a[r]);
ans[r-3][r-2]=Secret(a[r-3],a[r-2]);
ans[r-3][r]=Secret(ans[r-1][r],ans[r-3][r-2]);
ans[r-3][r-1]=Secret(ans[r-3][r-2],a[r-1]);
}
else{
int k=a[m+1];
for(int i=m+2;i<=r;i++){
k=Secret(k,a[i]);
ans[m+1][i]=k;
}
}
return;
}
int m=l+r>>1;
int k=a[m];
ans[m][m]=a[m];
for(int i=m-1;i>=l;i--){
k=Secret(a[i],k);
ans[i][m]=k;
}
k=a[m+1];
ans[m+1][m+1]=a[m+1];
for(int i=m+2;i<=r;i++){
k=Secret(k,a[i]);
ans[m+1][i]=k;
}
build(l,m-1,height+1);
build(m+2,r,height+1);
}
int query(int l,int r,int height,int L,int R){
int m=l+r>>1;
if(L<=m && m<=R){
if(m==R){
return ans[L][m];
}
else return Secret(ans[L][m],(m+1==R?a[R]:ans[m+1][R]));
}
if(L<=(m+1) && (m+1)<=R){
if(m+1==L){
return ans[m+1][R];
}
else return Secret((m==L?a[L]:ans[L][m]),ans[m+1][R]);
}
if(height==9){
if(m>R){
if(R-L==2){
return Secret(ans[L][L+1],a[L+2]);
}
else{
return Secret(a[L],a[R]);
}
}
if(L>m+1){
if(R-L==2){
return Secret(a[R-2],ans[R-1][R]);
}
else return Secret(a[L],a[R]);
}
}
if(m>R){
return query(l,m-1,height+1,L,R);
}
else return query(m+1,r,height+1,L,R);
}
void Init(int N, int A[]){
n=N;
for(int i=0;i<n;i++) a[i]=A[i];
build(0,n-1,1);
}
int Query(int L, int R) {
if(L==R) return a[L];
return query(0,n-1,1,L,R);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |