제출 #574722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574722		MadokaMagicaFan	비밀 (JOI14_secret)	C++14	100 / 100	445 ms	4640 KiB

secret

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