Submission #1010234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010234		LilPluton	Addk (eJOI21_addk)	C++14	0 / 100	157 ms	4952 KiB

Main

#include <bits/stdc++.h>
/// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
using namespace std;

#define ll  long long

const int N = 1e5 + 5;

int n, k, q, l, r, m, ty;
int a[N], lz[N * 4], t[4 * N];

 
void relax(int id, int l, int r){
    if (!lz[id]) return;
    int m = (l + r) >> 1;
 
    t[id << 1] += (m - l + 1) * lz[id];
    t[id << 1 | 1] += (r - m) * lz[id];
    lz[id << 1] += lz[id];
    lz[id << 1 | 1] += lz[id];
    lz[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val){
    if (u > r || v < l) return;
    if (u <= l && v >= r){
        t[id] += (r - l + 1) * val;
        lz[id] += val;
        return;
    }
    int m = (l + r) >> 1;
    relax(id, l, r);
    update(id << 1, l, m, u, v, val);
    update(id << 1 | 1, m + 1, r, u, v, val);
    t[id] = t[id << 1] + t[id << 1 | 1];
}

int getans(int id, int l, int r, int u, int v){
    if (u > r || v < l) return 0;
    if (u <= l && v >= r) return t[id];
    int m = (l + r) >> 1;
    relax(id, l, r);
    int ql = getans(id << 1, l, m, u, v);
    int qr = getans(id << 1 | 1, m + 1, r, u, v);
    return (ql + qr);
}

signed main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> a[i], update(1,1,n,i,n,a[i]);
	cin >> q;
	while(q--)
	{
		cin >> ty;
		if(ty == 1)
		{
			vector<int>pos(k), val;
			for(int &v : pos)
				cin >> v;
			for(int j = 1; j < k; ++j)
				val.push_back(a[pos[j]]);
			val.push_back(a[pos[0]]);
			for(int j = 0; j < k; ++j)
			{
				update(1,1,n,pos[j], n, val[j] - a[pos[j]]);
				a[pos[j]] = val[j];
			}
		}
		else
		{
			cin >> l >> r >> m;
			cout << getans(1,1,n,l + m - 1, r) - getans(1,1, n, l - 1, r - m) << endl;
		}
	}
}

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