oj.uz

Submission #949740

# Submission time Handle Problem Language Result Execution time Memory
949740 2024-03-19T15:33:15 Z amirhoseinfar1385 Secret (JOI14_secret) C++17
100 / 100
 397 ms 8360 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#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 6752 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 6736 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 111 ms 6700 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 397 ms 8276 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 396 ms 8276 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 393 ms 8272 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 395 ms 8360 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 390 ms 8360 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 386 ms 8272 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 397 ms 8272 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1