oj.uz

Submission #1090213

# Submission time Handle Problem Language Result Execution time Memory
1090213 2024-09-18T03:00:51 Z efishel Secret (JOI14_secret) C++17
100 / 100
 330 ms 4584 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2560 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 2560 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 86 ms 2520 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 310 ms 4484 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 314 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 330 ms 4576 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 303 ms 4336 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 309 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 330 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 310 ms 4584 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1