제출 #1197188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197188		Johan	Addk (eJOI21_addk)	C++20	100 / 100	651 ms	9676 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double	
  
const int MAX = 2e5 + 6;
const int LOG = 26;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int block = 320;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int st_pr[MAX * 4], st_a[MAX * 4], lzy[MAX * 4];
void relax(int v, int l, int r){
	if(lzy[v] == 0)	return;
	if(l != r){
		lzy[v * 2] += lzy[v];
		lzy[v * 2 + 1] += lzy[v];
	}
	st_pr[v] += (r - l + 1) * lzy[v];
	lzy[v] = 0;
}
void upd(int v, int l, int r, int ul, int ur, int x){
	relax(v, l, r);
	if(l > ur || r < ul)
		return;
	if(l >= ul && r <= ur){
		lzy[v] += x;
		relax(v, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	upd(v * 2, l, mid, ul, ur, x);
	upd(v * 2 + 1, mid + 1, r, ul, ur, x);
	st_pr[v] = st_pr[v * 2] + st_pr[v * 2 + 1];
}
void upd(int v, int l, int r, int pos, int val){
	if(l == r){
		st_a[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos)
		upd(v * 2, l, mid, pos, val);
	else
		upd(v * 2 + 1, mid + 1, r, pos, val);
	st_a[v] = st_a[v * 2] + st_a[v * 2 + 1];
}
int ask_a(int v, int l, int r, int ql, int qr){
	if(l > qr || r < ql)
		return 0;
	if(l >= ql && r <= qr)
		return st_a[v];
	int mid = (l + r) >> 1;
	return ask_a(v * 2, l, mid, ql, qr) + ask_a(v * 2 + 1, mid + 1, r, ql, qr);
}
int ask_pr(int v, int l, int r, int ql, int qr){
	relax(v, l, r);
	if(l > qr || r < ql)
		return 0;
	if(l >= ql && r <= qr)
		return st_pr[v];
	int mid = (l + r) >> 1;
	return ask_pr(v * 2, l, mid, ql, qr) + ask_pr(v * 2 + 1, mid + 1, r, ql, qr);
}
void _(){
	int n, k;
	cin >> n >> k;
	vector < int > a(n + 1);
	vector < int > pr(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pr[i] = pr[i - 1] + a[i];
		upd(1, 1, n, i, a[i]);
		upd(1, 1, n, i, i, pr[i]);
	}
//	for(int i  =1; i <= n; i++)
//		cout << pr[i] << ' ';
//	cout << endl;
	int q;
	cin >> q;
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int last;
			vector < int > idx;
			vector < int > num;
			for(int i = 1; i <= k; i++){
				int d;
				cin >> d;
				idx.push_back(d);
				if(i == 1){
					last = d;
					continue;
				}
				num.push_back(a[d]);
			}
			int dif = 0;
			num.push_back(a[last]);
//			for(auto i : idx)	cout << i << ' ';	cout << endl;
//			for(auto i : num)	cout << i << ' ';	cout << endl;
			for(int i = 0; i < k; i++){
				int val = num[i] - a[idx[i]];
				dif += val;
				int cur = (ask_pr(1, 1, n, idx[i] - 1, idx[i] - 1) + num[i]) - ask_pr(1, 1, n, idx[i], idx[i]);
				upd(1, 1, n, idx[i], idx[i], cur);
				upd(1, 1, n, idx[i] + 1, (i == k - 1 ? n : idx[i + 1] - 1), dif);
			}
			for(int i = 0; i < k; i++){
				upd(1, 1, n, idx[i], num[i]);
				a[idx[i]] = ask_a(1, 1, n, idx[i], idx[i]);	
			}
//			for(int i = 1; i <= n; i++)
//				pr[i] = ask_pr(1, 1, n, i, i);
//			for(int i = 1; i <= n; i++)
//				cout << pr[i] << ' ';
//			cout << endl;
		}
		else {
			int l, r, m;
			cin >> l >> r >> m;
			int rr = ask_pr(1, 1, n, l + m - 1, r);
			int ll = ask_pr(1, 1, n, l - 1, r - m);
//			cout << ll << '-' << rr << '-';
			cout << rr - ll << endl;
		}
	}
}
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)  _();
}

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