Submission #774948

#	Time	Username	Problem	Language	Result	Execution time	Memory
774948		tpd2k	Addk (eJOI21_addk)	C++14	92 / 100	1251 ms	7140 KiB

Main

// teddybear's code
// the one who loves NBP
// noe the second
// goal: 0 / 8
// get medal in APIO (like TKN)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

// prob: 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define FOR(i,n) for (int i = 0; i<n; i++)
using ll = long long;
using ull = unsigned long long;
ll n,m,t;
ll cnt = 0;
const int maxn = 1e5;
const ll mod = 1e9 + 7;
#define Y "YES"
#define N "NO"

bool visited[1005][1005];
int dist[1005][1005];
int w,h;
int fx[4] = {-1, 1, 0, 0};
int fy[4] = {0, 0, -1, 1};
queue <pair<int,int>> q;

ll st[4 * maxn + 5];
ll a[maxn + 5];

void build(int id, int l, int r)
{
	if (l == r)
	{
		st[id] = a[l];
		return;
	}
	
	int m = (l + r) / 2;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	
	st[id] = st[id*2] + st[id*2+1];
}

void update(int id, int l, int r, int lq, int rq, ll val)
{
	if (l > rq || r < lq)
	{
		return;
	}
	if (l >= lq && r <= rq)
	{
		st[id] = val;
		return;
	}
	
	int m = (l + r) / 2;
	update(id*2,l,m,lq,rq,val);
	update(id*2+1,m+1,r,lq,rq,val);
	
	st[id] = st[id*2] + st[id*2+1];
	
}

ll get(int id, int l, int r, int lq, int rq)
{
	if (l > rq || r < lq)
	{
		return 0;
	}
	if (l >= lq && r <= rq)
	{
		return st[id];
	}
	int m = (l + r) / 2;
	return get(id*2,l,m,lq,rq) + get(id*2+1,m+1,r,lq,rq);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i<=n; i++)
	{
		cin >> a[i];
	}
	build(1,1,n);
	cin >> t;
	while (t--)
	{
		int num;
		cin >> num;
		if (num == 1)
		{
			ll change[11];
			
			for (int i = 0; i<m; i++)
			{
				cin >> change[i];
			}
			if (m == 1)
			{
				continue;
			}
			ll z = change[0];
			for (int i = 0; i<m-1; i++)
			{
				a[change[i]] = a[change[i+1]];
				update(1,1,n,change[i],change[i],a[change[i]]);
			}
			a[change[m-1]] = a[z];
			update(1,1,n,change[m-1],change[m-1],a[change[m-1]]);
		}
		else
		{
			ll x,y,dis;
			cin >> x >> y >> dis;
			ll total = get(1,1,n,x,y);
			ll x1 = x, y1 = y;
			ll sum = 0;
			ll dem = 0;
			while (x1 <= y1 && y1 >= x + dis - 1 && dem < dis)
			{
				sum += total;
				total -= a[x1];
				total -= a[y1];
				y1--;
				x1++;
				dem++;
				//cout << "! " << sum << '\n';
			}
			cout << sum << '\n';
		}
	}
}

/*
8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3

8 3
7 2 5 1 9 3 4 6
1
2 2 7 4


*/

void init()
{
 	int te = 1; //cin >> te;
 	while (te--)
 	{
 	 	  solve();
 	}
}

void preprocess()
{

}


int main()
{
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL);
    //cin.tie(0); cout.tie(0);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
 	init();
 	preprocess();
 	//solve();
 	return 0;
}

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