Submission #715291

#	Time	Username	Problem	Language	Result	Execution time	Memory
715291		Nonoze	Addk (eJOI21_addk)	C++17	0 / 100	132 ms	8068 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string;

#define int ll
#define MN 1e5+5
#define MOD 1000000007
#define endl '\n'
#define endlfl endl << flush
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
const int INF=1e9 + 10;

const auto beg = std::chrono::high_resolution_clock::now();
void dbg_time() {
	auto us = (double)std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now() - beg).count();
	cerr << "Operation time: " << (long double)us/1000000 << " seconds." << endl;
}


struct node
{
	node* left, *right;
	int sum;
	void update()
	{
		sum=left->sum+right->sum;
	}
};

int query(node* root, int left, int right, int qLeft, int qRight)
{
	if (left>qRight || right<qLeft) return 0;
	if (left>=qLeft && right<=qRight) return root->sum;

	int mid=(left+right)/2;
	return query(root->left, left, mid, qLeft, qRight)+query(root->right, mid+1, right, qLeft, qRight);
}

void update(node* root, int left, int right, int qLeft, int qRight, int nValue)
{
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight)
	{
		root->sum=nValue;
		return;
	}

	int mid=(left+right)/2;
	update(root->left, left, mid, qLeft, qRight, nValue);
	update(root->right, mid+1, right, qLeft, qRight, nValue);
	root->update();
}

void build(node* root, int left, int right, const vector<int> &v)
{
	if (left==right)
	{
		root->sum=v[left];
		return;
	}

	root->left=new node{NULL, NULL, 0};
	root->right=new node{NULL, NULL, 0};

	int mid=(left+right)/2;
	build(root->left, left, mid, v);
	build(root->right, mid+1, right, v);
	root->update();
}

void destroy(node* root)
{
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

int n, k, q;

void solve()
{
	cin >> n >> k;
	vector<int> a(n+1);
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	node* root=new node{NULL, NULL, 0};
	build(root, 1, n, a);
	cin >> q;
	while(q--) {
		int action; cin >> action;
		if (action==1) {
			int input; cin >> input;
		} else {
			int l, r, m; cin >> l >> r >> m;
			int sum=query(root, 1, n, l, r)*m;
			cout << sum << " ";
			for (int i = 0; i < m-1; ++i)
			{
				sum-=a[l+i]*(m-i-1);
				sum-=a[r-i]*(m-i-1);
			}
			cout << sum << endl;
		}
	}
	destroy(root);
	return;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	dbg_time();
	return 0;
}

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