oj.uz

Submission #1003692

# Submission time Handle Problem Language Result Execution time Memory
1003692 2024-06-20T15:37:00 Z MarwenElarbi Secret (JOI14_secret) C++17
100 / 100
 287 ms 8400 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int MAXN=1e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[1005][1005];
int n;
int Secret(int X, int Y);
void daq(int l,int r){
  if(r-l<2) return;
  int mid=(r+l)/2;
  dp[mid][mid+1]=dp[mid+1][mid+1];
  for (int i = mid+2; i <= r; ++i)
  {
    dp[mid][i]=Secret(dp[mid][i-1],dp[i][i]);
  }
  for (int i = mid-1; i >= l ; --i)
  {
    dp[mid][i]=Secret(dp[i][i],dp[mid][i+1]);
  }
  daq(l,mid);
  daq(mid+1,r);
  return;
}
void Init(int N, int A[]) {
  n=N;
    for (int i = 0; i < N; ++i)
    {
        dp[i][i]=A[i];
    }
    daq(0,N-1);
    return;
}
int query(int l,int r,int left,int right){
    int mid=(r+l)/2;
    if(left>mid) return query(mid+1,r,left,right);
    else if(right<mid) return query(l,mid,left,right);
    else if(left==mid) return Secret(dp[mid][mid],dp[mid][right]);
    else if(right==mid) return dp[mid][left];
    else{
        //cout <<dp[mid][right]<<" "<<dp[mid][left]<<endl;
        return Secret(dp[mid][left],dp[mid][right]);
    }
}
int Query(int L, int R) {
    if(R==L) return dp[L][L];
    else if(R-L==1) return Secret(dp[L][L],dp[R][R]);
    else{
        return query(0,n-1,L,R);
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 4656 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 82 ms 4436 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 85 ms 4416 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 283 ms 8272 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 287 ms 8376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 269 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 283 ms 8400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 274 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 273 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 282 ms 8244 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1