Submission #550367

#	Time	Username	Problem	Language	Result	Execution time	Memory
550367		farhan132	Secret (JOI14_secret)	C++17	100 / 100	449 ms	8612 KiB

secret

#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 / 100