oj.uz

Submission #471517

# Submission time Handle Problem Language Result Execution time Memory
471517 2021-09-09T16:00:55 Z UltraFalcon Addk (eJOI21_addk) C++17
100 / 100
 524 ms 24416 KB 
#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#endif

#include <bits/stdc++.h>
#define int long long

#define d_struct tuple<int, int, int>

using namespace std;

struct Segtree {
    int n;
    vector<d_struct> data;

    Segtree(const vector<int>& v) {
        n = v.size();
        data = vector<d_struct>(4*n);
        build(v, 1, 0, n);
    }

    public:
    void set(int i, int x) {
        set(i, x, 1, 0, n);
    }

    int query(int beg, int ed) {
        return get<0>(query(beg, ed, 1, 0, n));
    }

    private:
    d_struct combine(d_struct a, d_struct b) {
        auto [res1, flat1, h1] = a;
        auto [res2, flat2, h2] = b;
        return {res1 + (res2 + (flat2 * h1)), flat1 + flat2, h1 + h2};
    }

    void update(int pos) {
        data[pos] = combine(data[pos*2], data[pos*2+1]);
    }

    void build(const vector<int>& v, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = {v[left], v[left], 1};
        } else {
            int mid = (left+right) / 2;
            build(v, pos*2, left, mid);
            build(v, pos*2+1, mid, right);
            update(pos);
        }
    }

    void set(int i, int x, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = {x, x, 1};
        } else {
            int mid = (left+right) / 2;
            if (i < mid) {
                set(i, x, pos*2, left, mid);
            } else {
                set(i, x, pos*2+1, mid, right);
            }
            update(pos);
        }
    }

    d_struct query(int beg, int ed, int pos, int left, int right) {
        if (beg <= left && ed >= right) {
            return data[pos];
        } else if (ed <= left || beg >= right) {
            return {0, 0, 0};
        } else {
            int mid = (left+right) / 2;
            return (combine(query(beg, ed, pos*2, left, mid),
                            query(beg, ed, pos*2+1, mid, right)));
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    vector<int> a_rev(n);
    for (int i=0; i<n; i++) {
        int ai;
        cin >> ai;
        a[i] = ai;
        a_rev[i] = ai;
    }
    reverse(a_rev.begin(), a_rev.end());

    Segtree s_inc(a);
    Segtree s_dec(a_rev);

    int q;
    cin >> q;

    for (int i=0; i<q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            vector<int> idx(k);
            for (int j=0; j<k; j++) {
                cin >> idx[j];
            }
            int tmp = a[idx[0]-1];
            for (int j=0; j<(k-1); j++) {
                s_inc.set(idx[j]-1, a[idx[j+1]-1]);
                s_dec.set(n-idx[j], a[idx[j+1]-1]);
                a[idx[j]-1] = a[idx[j+1]-1];
            }
            s_inc.set(idx[k-1]-1, tmp);
            s_dec.set(n-idx[k-1], tmp);
            a[idx[k-1]-1] = tmp;

        } else {
            int l, r, m;
            cin >> l >> r >> m;

            m = min(m, (r - l + 1) - m + 1);

            int sum = 0;
            if ((r - l + 1) % 2 == 0) {
                sum += s_inc.query(l-1, (l - 1) + ((r - l + 1) / 2));
                sum += s_dec.query(n-r, (n - r) + ((r - l + 1) / 2));
                //cerr << "run1";
                if (m < ((r - l + 1) / 2)) {
                    sum -= s_inc.query(l+m-1, (l - 1) + ((r - l + 1) / 2));
                    sum -= s_dec.query(n-(r-m), (n - r) + ((r - l + 1) / 2));
                }
            } else {
                sum += s_inc.query(l-1, (l - 1) + ((r - l + 2) / 2));
                sum += s_dec.query(n-r, (n - r) + ((r - l + 1) / 2));
                //cerr << sum << "\n";
                if (m == ((r - l + 1) / 2)) {
                    sum -= a[(l-1) + ((r - l + 1) / 2)];
                } else if (m < ((r - l + 1) / 2)) {
                    sum -= s_inc.query(l+m-1, (l - 1) + ((r - l + 2) / 2));
                    sum -= s_dec.query(n-(r-m), (n - r) + ((r - l + 1) / 2));
                }
            }
            cout << sum << "\n";
        }
    }

}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 8 ms 1100 KB Output is correct
6 Correct 10 ms 1356 KB Output is correct
7 Correct 13 ms 1556 KB Output is correct
8 Correct 14 ms 1796 KB Output is correct
9 Correct 21 ms 2508 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4748 KB Output is correct
2 Correct 75 ms 6980 KB Output is correct
3 Correct 133 ms 9832 KB Output is correct
4 Correct 208 ms 16188 KB Output is correct
5 Correct 329 ms 22860 KB Output is correct
6 Correct 264 ms 22156 KB Output is correct
7 Correct 298 ms 22820 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 11400 KB Output is correct
2 Correct 321 ms 18836 KB Output is correct
3 Correct 524 ms 22704 KB Output is correct
4 Correct 333 ms 24416 KB Output is correct