Submission #775022

#	Time	Username	Problem	Language	Result	Execution time	Memory
775022		anhduc2701	Addk (eJOI21_addk)	C++17	100 / 100	227 ms	14280 KiB

Main

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k, q;
int a[maxn];
struct node
{
    int s1, s2, len, sum;
    node() {}
    node(int x)
    {
        s1 = x;
        s2 = x;
        len = 1;
        sum = x;
    }
    node operator+(const node &x)
    {
        node ans;
        ans.s1 = x.sum * len + s1 + x.s1;
        ans.s2 = sum * x.len + s2 + x.s2;
        ans.sum = x.sum + sum;
        ans.len = len + x.len;
        return ans;
    }
} st[maxn];
void build(int id, int l, int r)
{
    if (l == r)
    {
        st[id] = node(a[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}
void update(int id, int l, int r, int u, int val)
{
    if (r < u || u < l)
        return;
    if (l == r)
    {
        st[id] = node(val);
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, val);
    update(id * 2 + 1, mid + 1, r, u, val);
    st[id] = st[id * 2] + st[id * 2 + 1];
}
node get(int id, int l, int r, int u, int v)
{
    if (u == l && r == v)
    {
        return st[id];
    }
    int mid = (l + r) / 2;
    if (mid >= v)
        return get(id * 2, l, mid, u, v);
    if (mid < u)
        return get(id * 2 + 1, mid + 1, r, u, v);
    return get(id * 2, l, mid, u, mid) + get(id * 2 + 1, mid + 1, r, mid + 1, v);
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    cin >> q;

    for (int i = 1; i <= q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            vector<int> pos;
            for (int j = 1; j <= k; j++)
            {
                int vt;
                cin >> vt;
                pos.pb(vt);
            }
            update(1, 1, n, pos.back(), a[pos[0]]);
            int vt = a[pos.back()];
            a[pos.back()] = a[pos[0]];
            for (int j = k - 2; j >= 0; j--)
            {
                update(1, 1, n, pos[j], vt);

                int luu = vt;
                vt = a[pos[j]];
                a[pos[j]] = luu;
            }
        }
        else
        {

            int l, r, m;
            cin >> l >> r >> m;
            /*
            int sum = 0;
            for (int i = l + m - 1; i <= r; i++)
            {
                for (int j = i - m + 1; j <= i; j++)
                {
                    sum += a[j];
                }
            }
            cout << sum << " ";
            */
            int ans = 0;
            if (r - l + 1 == m)
            {
                node k = get(1, 1, n, l, r);
                cout << k.sum << "\n";
            }
            else
            {

                int d1 = min(l + m - 1, r - m + 1);
                int d2 = max(d1 + 1, max(r - m + 1, l + m - 1));
                ans += get(1, 1, n, l, d1).s1;
                ans += get(1, 1, n, d2, r).s2;
                if (d1 + 1 < d2)
                {
                    ans += get(1, 1, n, d1 + 1, d2 - 1).sum * min(m, r - m + 1 - l + 1);
                }
                cout << ans << "\n";
            }
        }
    }
}

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