oj.uz

Submission #949736

# Submission time Handle Problem Language Result Execution time Memory
949736 2024-03-19T15:31:58 Z amirhoseinfar1385 Secret (JOI14_secret) C++17
100 / 100
 394 ms 8284 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,all[maxn],dp[maxn][maxn];

int pors(int l,int r){
  if(l==r){
    return all[l];
  }
  return Secret(all[l],dp[l+1][r]);
}

int pors2(int l,int r){
  if(l==r){
    return all[l];
  }
  return Secret(dp[r-1][l-1],all[r]);
}

void create(int l,int r){
  if(l>r){
    return ;
  }
  int m=(l+r)>>1;
  for(int i=m;i>=l;i--){
    dp[i][m]=pors(i,m);
    //cout<<i<<" "<<m<<" "<<dp[i][m]<<"\n";
  }
  for(int i=m+1;i<=r;i++){
    dp[i][m]=pors2(m+1,i);
    //cout<<i<<" "<<m<<" "<<dp[i][m]<<"\n";
  }
  create(m+1,r);
  create(l,m-1);
}

void Init(int N, int A[]) {
  n=N;
  for(int i=0;i<n;i++){
    all[i]=A[i];
  }
  create(0,n-1);
}

int solve(int l,int r,int tl=0,int tr=n-1){
  int m=(tl+tr)>>1;
  if(l>m&&r>m){
    return solve(l,r,m+1,tr);
  }
  if(l<m&&r<m){
    return solve(l,r,tl,m-1);
  }
  if(l==m){
    return Secret(all[l],dp[r][m]);
  }
  if(r==m){
    return dp[l][m];
  }
  //cout<<l<<" "<<m<<" "<<r<<" "<<dp[l][m]<<" "<<dp[r][m]<<"\n";
  return Secret(dp[l][m],dp[r][m]);
}
  
int Query(int L, int R) {
  if(L==R){
    return all[L];
  }
  return solve(L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 6760 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 116 ms 6740 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 6748 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 381 ms 8144 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 378 ms 8244 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 394 ms 8176 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 389 ms 8284 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 389 ms 8280 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 390 ms 8280 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 382 ms 8128 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1