Submission #1090213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090213		efishel	Secret (JOI14_secret)	C++17	100 / 100	330 ms	4584 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

struct si { int v; };
si operator+ (si a, si b) { return si{ Secret(a.v, b.v) }; }
using vsi = vector <si>;

const ll MAXN = 1E3+16, LOG = 11;
si suff[LOG][MAXN], pref[LOG][MAXN];
vsi ve;

#define mid ((l+r)>>1)
void finit (ll l, ll r, ll lvl) {
    suff[lvl][mid] = ve[mid];
    for (ll i = mid-1; i >= l; i--)
        suff[lvl][i] = ve[i] + suff[lvl][i+1];
    pref[lvl][mid+1] = ve[mid+1];
    for (ll i = mid+2; i <= r; i++)
        pref[lvl][i] = pref[lvl][i-1] + ve[i];
    if (l == r) return;
    finit(l, mid, lvl+1);
    finit(mid+1, r, lvl+1);
}

ll n;
void Init (int n, int a[]) {
    ::n = n;
    ve = vsi(n, si{ 0 });
    for (ll i = 0; i < n; i++) ve[i] = si{ a[i] };
    finit(0, n-1, 0);
}

si fsolve (ll ql, ll qr, ll l, ll r, ll lvl) {
    if (ql <= mid && mid+1 <= qr) {
        return suff[lvl][ql] + pref[lvl][qr];
    }
    if (qr <= mid)
        return fsolve(ql, qr, l, mid, lvl+1);
    else
        return fsolve(ql, qr, mid+1, r, lvl+1);
}

int Query (int ql, int qr) {
    if (ql == qr) return ve[ql].v;
    return fsolve(ql, qr, 0, n-1, 0).v;
}

• Subtask 1: 100 / 100