oj.uz

Submission #1010234

# Submission time Handle Problem Language Result Execution time Memory
1010234 2024-06-28T14:05:54 Z LilPluton Addk (eJOI21_addk) C++14
0 / 100
 157 ms 4952 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Incorrect 5 ms 2508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -