oj.uz

Submission #574722

# Submission time Handle Problem Language Result Execution time Memory
574722 2022-06-09T10:23:29 Z MadokaMagicaFan Secret (JOI14_secret) C++14
100 / 100
 445 ms 4640 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

int n;

int Secret(int X, int Y);

struct SGT{
    vector<int> t;
    vector<vector<int>> p;
    vector<vector<int>> s;

    int n;
    int *a;

    SGT()
    {
    }

    void
    init(int _n, int *_a) 
    {
        a = _a;
        n = _n;
        t.resize(4*n);
        p.resize(4*n);
        s.resize(4*n);

        build(1,0,n-1);
    }

    int
    queryval(int i, int l, int r, int tl, int tr)
    {
        if (l > tr || r < tl) return 0;
        if (tl < l && tr > r) return 0;
        if (tl == l && tr == r) return t[i];

        int mid = (l+r)>>1;

        if (l == r)
            return t[i];
        if (tl == l) {
            if (tr <= mid) {
                return queryval(i<<1,l,mid,tl,tr);
            } else {
                return p[i][tr - mid-1];
            }
        }

        if (tr == r) {
            if (tl > mid) {
                return queryval(i<<1|1,mid+1,r,tl,tr);
            } else {
                return s[i][mid-tl];
            }
        }

        if (tl == mid+1)
            return queryval(i<<1|1, mid+1, r, tl, tr);
        if (tr == mid)
            return queryval(i<<1, l, mid, tl, tr);
        assert(0);
        return queryval(i<<1, l, mid, tl, tr) + queryval(i<<1|1, mid+1, r, tl, tr);
    }

    void
    build(int i, int l, int r)
    {
        if (l == r) {
            p[i].pb(a[l]);
            s[i].pb(a[l]);
            t[i] = a[l];
            return;
        }

        int mid = (l+r)>>1;

        build(i<<1, l, mid);
        build(i<<1|1, mid+1, r);

        if (i == 1) return;

        for (int j = mid+1; j <= r; ++j) {
            p[i].pb(Secret(t[i<<1],queryval(i<<1|1,mid+1,r,mid+1,j)));
        }

        for (int j = mid; j > l; --j) {
            s[i].pb(Secret(queryval(i<<1,l,mid,j,mid),t[i<<1|1]));
        }

        t[i] = p[i][sz(p[i])-1];
        return;
    }

    int
    query(int i, int l, int r, int tl, int tr)
    {
        if (l == r) return t[i];
        if (i != 1) {
            if (l == tl && r == tr) {
                return t[i];
            }

            if (l > tr || r < tl) return 0;
            if (tr > r || l > tl) assert(0);

            if (l == tl)
                return queryval(i,l,r,tl,tr);
            if (r == tr)
                return queryval(i,l,r,tl,tr);
        }
        int mid = (l+r)>>1;
        if (tl > mid) return query(i<<1|1,mid+1,r,tl,tr);
        if (tr < mid+1) return query(i<<1,l,mid,tl,tr);

        return Secret(queryval(i<<1,l,mid,tl,mid),
                queryval(i<<1|1,mid+1,r,mid+1,tr));
    }

    int query(int l, int r) { return query(1,0,n-1,l,r); }
};

SGT tr;

void
Init(int _n, int a[])
{
    n = _n;
    tr.init(n,a);
    return;
}

int
Query(int l, int r)
{
    return tr.query(l,r);
}


#ifdef ONPC
int
Secret(int X, int Y)
{
    return X + Y;
}

void
solve()
{
    int _n;
    int q;
    cin >> _n >> q;
    int a[_n];
    for (int i = 0; i < _n; ++i)
        cin >> a[i];

    Init(_n,a);

    int x, y;
    while (q--) {
        cin >> x >> y;
        --x,--y;
        cout << Query(x, y) << endl;
    }
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 2512 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 119 ms 2468 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 121 ms 2464 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 423 ms 4524 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 423 ms 4596 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 422 ms 4496 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 431 ms 4640 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 427 ms 4564 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 445 ms 4548 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 419 ms 4564 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1