oj.uz

Submission #550367

# Submission time Handle Problem Language Result Execution time Memory
550367 2022-04-18T00:26:25 Z farhan132 Secret (JOI14_secret) C++17
100 / 100
 449 ms 8612 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 1005;
ll sum[N][N], a[N];

void dq(ll l, ll r){
  if(r - l + 1 <= 2) return;
  ll m = (l + r)/2;
  sum[m][m] = a[m];
  for(ll i = m-1; i >= l; i--) sum[i][m] = Secret(a[i], sum[i + 1][m]);
  sum[m + 1][m + 1] = a[m + 1];
  for(ll i = m + 2; i <= r; i++) sum[m + 1][i] = Secret(sum[m + 1][i-1], a[i]);
  dq(l, m-1);
  dq(m + 2, r);
  return;
}
ll query(ll l, ll r, ll x, ll y){
  if(r < l || r < x || y < l) return 0;
  if(r - l + 1 <= 2){
    if(y - x + 1 == 1) return a[x];
    return Secret(a[x], a[y]);
  }
  ll m = (l + r)/2;
  if(y == m || x == m + 1){
   return sum[x][y];
  }
  if(x <= m && y > m){
    return Secret(sum[x][m], sum[m+1][y]);
  }
  return query(l,m-1,x,y) + query(m + 2, r, x, y);
}
ll _n;
void Init(int n, int A[]) {
  for(ll i = 1; i <= n; i++) a[i] = A[i - 1]; 
  dq(1, n);
  _n = n;
  return;
}

int Query(int L, int R) {
  return query(1, _n, L + 1, R + 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4408 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 129 ms 4488 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 123 ms 4392 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 443 ms 8304 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 439 ms 8236 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 438 ms 8192 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 442 ms 8612 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 449 ms 8236 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 439 ms 8280 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 441 ms 8208 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1