Submission #1172774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172774		nagibator	Addk (eJOI21_addk)	C++20	36 / 100	2095 ms	2256 KiB

Main

#include <bits/stdc++.h>
#define nn '\n'
#pragma GCC optimize("O3")
#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#define pb push_back
#define all(x) x.begin(), x.end()
#define sec second
#define vec std::vector
using namespace std;
const int N = 2e5 + 2;
const int inf = 1e15;
const int mod = 1e9 + 7;
int T = 1, a[N], t[4 * N], add[4 * N];
void push( int v, int tl, int tr )
{
	if( add[v] == 0 )
		return;
	t[v] += (tr - tl + 1) * add[v];
	if( tl < tr )
	{
		add[v + v] += add[v];
		add[v + v + 1] += add[v];
	}
	add[v] = 0;
}
void build( int v, int tl, int tr )
{
	if( tl == tr )
	{
		t[v] = a[tl];
		return;
	}
	int mid = (tl + tr) / 2;
	build(v + v, tl, mid);
	build(v + v + 1, mid + 1, tr);
	t[v] = t[v + v] + t[v + v + 1];
}
void upd( int v, int tl, int tr, int l, int r, int x )
{
	push(v, tl, tr);
	if( tr < l || r < tl )
		return;
	if( l <= tl && tr <= r )
	{
		add[v] += x;
		push(v, tl, tr);
		return;
	}
	int mid = (tl + tr) / 2;
	upd(v + v, tl, mid, l, r, x);
	upd(v + v + 1, mid + 1, tr, l, r, x);
	t[v] = t[v + v] + t[v + v + 1];
}
int get( int v, int tl, int tr, int l, int r )
{
	push(v, tl, tr);
	if( tr < l || r < tl )
		return 0;
	if( l <= tl && tr <= r )
		return t[v];
	int mid = (tl + tr) / 2;
	int x = get(v + v, tl, mid, l, r);
	int y = get(v + v + 1, mid + 1, tr, l, r);
	return x + y;
}
vec<pair<int,int>> p;
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int n, k;
    cin >> n >> k;
    vec<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            vec<int> b(k);
            for (int i = 0; i < k; i++) {
                cin >> b[i];
            }
            int pos  = a[b[0]];
            for (int i = 0; i < k  - 1; i++) {
                a[b[i]] = a[b[i + 1]];
            }
            a[b[k - 1]] = pos;
        } else {
            int l ,r ,m;
            cin >> l >> r>> m;
            l--;r--;
           vector<int> pref(r - l + 2, 0);
            for (int i = 0; i <= r - l; ++i) {
                pref[i + 1] = pref[i] + a[l + i];
            }
            int sum = 0;
            for (int i = 0; i <= (r - l + 1) - m; ++i) {
                sum += pref[i + m] - pref[i];
            }
            cout << sum << nn;
        }
    }
}

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