제출 #1263039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263039		Ekber_Ekber	Addk (eJOI21_addk)	C++20	100 / 100	164 ms	16016 KiB

Main

#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;

struct SegTree{
    int n;
    vector <int> a;
    vector <array<int, 4>> t;   // [0] - sum    [1] - pr sum    [2] - sf sum    [3] - size
    void init(int n1, vector <int> &v) {
        n = n1;
        a = v;
        t.resize(4*(n+2));
    }
    array <int, 4> merge(array <int, 4> a, array <int, 4> b) {
        return {a[0] + b[0], a[1] + b[1] + b[0] * a[3], b[2] + a[2] + a[0] * b[3], a[3] + b[3]};       // TODO
    }
    void build(int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = {a[tl], a[tl], a[tl], 1};
            return;
        }
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
    array<int, 4> find(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            array <int, 4> x;
            x[0] = x[1] = x[2] = x[3] = 0;
            return x;
        }      // TODO
        if (tl == l && tr == r) return t[v];
        int tm = (tl + tr) / 2;
        array <int, 4> r1 = find(v*2, tl, tm, l, min(r, tm));
        array <int, 4> r2 = find(v*2+1, tm+1, tr, max(l, tm+1), r);
        return merge(r1, r2);
    }
    void update(int v, int tl, int tr, int i, int x) {
        if (tl == tr) {
            t[v] = {x, x, x, 1};
            a[tl] = x;
            return;
        }
        int tm = (tl + tr) / 2;
        if (i <= tm) update(v*2, tl, tm, i, x);
        else update(v*2+1, tm+1, tr, i, x);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
    array <int, 4> get(int l, int r) {
        return find(1, 0, n-1, l, r);
    }
    void upd(int i, int x) {
        update(1, 0, n-1, i, x);
    }
};

void _() {
    int n, k;
    cin >> n >> k;
    vector <int> v(n);
    for (int &i : v) cin >> i;
    SegTree t;
    t.init(n, v);
    t.build(1, 0, n-1);
    int q;
    cin >> q;
    while (q--) {
        int d;
        cin >> d;
        if (d == 1) {
            vector <int> id(k);
            for (int &i : id) cin >> i, i--;
            vector <int> x(k);
            for (int i=0; i < k; i++) {
                x[i] = v[id[(i + 1) % k]];
            }
            for (int i=0; i < k; i++) {
                t.upd(id[i], x[i]);
            }
            for (int i = k-1; i > 0; i--) {
                swap(v[id[i]], v[id[0]]);
            }
        }
        else {
            int l, r, m;
            cin >> l >> r >> m;
            --l, --r;
            if (m == 1) {
                cout << t.get(l, r)[0] << endl;
                continue;
            }
            if (2 * (m - 1) > r - l + 1) m = r - l + 2 - m;
            if (2 * (m - 1) <= r - l + 1) {
                int res = t.get(l, l + m - 2)[1] + t.get(r - m + 2, r)[2];
                // cout << l << ' ' <<l + m - 2 << ' ' << t.get(l, l + m - 2)[1] << endl;
                if (l + m - 1 <= r - m + 1) {
                    res += t.get(l + m - 1, r - m + 1)[0] * m;
                    // cout << "x" << ' ';
                }
                cout << res << endl;
                continue;
            }
            else cout << "I think this is impossible!!!";
        }
    }
}

signed main() {

    GOOD_LUCK

    int tests=1;
    // cin >> tests;
    for (int i=1; i <= tests; i++) {
        _();
        // cout << endl;
    }

    return 0;
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8