Submission #626709

#	Time	Username	Problem	Language	Result	Execution time	Memory
626709		lovrot	Addk (eJOI21_addk)	C++11	100 / 100	211 ms	14524 KiB

Main

#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const int LOG = 17;
const int OFF = (1 << LOG);

struct node{ 
	ll len = 0;
	ll sum = 0;
	ll dsc = 0;
	ll asc = 0;
	node(){};
} tour[OFF * 2];

int n, q, c;
ll niz[OFF];
pair<ll, ll> cir[20];

node merge(node a, node b){ 
	node ret;
	ret.len = a.len + b.len;
	ret.sum = a.sum + b.sum;
	ret.asc = a.asc + a.len * b.sum + b.asc;
	ret.dsc = a.dsc + b.len * a.sum + b.dsc;
	return ret;
}

void update(int x, ll val){ 
	x += OFF;
	tour[x].sum = tour[x].asc = tour[x].dsc = val;
	x >>= 1;
	while(x){ 
		tour[x] = merge(tour[x * 2], tour[x * 2 + 1]);
		x >>= 1;
	}
}

node query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
	if(r <= lo || hi <= l) return node();
	if(l <= lo && hi <= r) return tour[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, lo, mi, x * 2), query(l, r, mi, hi, x * 2 + 1));
}

void init(){ 
	cin >> n >> c;
	pri(i, 0, n, 1){ 
		cin >> niz[i];
		tour[i + OFF].len = 1;
		tour[i + OFF].sum = tour[i + OFF].asc = tour[i + OFF].dsc = niz[i];
	}
	od(i, OFF - 1, 0, 1) tour[i] = merge(tour[i * 2], tour[i * 2 + 1]);
}

int nxt(int x){ 
	return (x + c + 1) % c;
}

int main(){ 
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	init();

	cin >> q;

	pri(i, 0, q, 1) {
		int t;
		cin >> t;
		if(t == 1){ 
			pri(j, 0, c, 1){
				int x;
				cin >> x;
				x--;
				cir[j] = {x, niz[x]};	
			} 
			pri(j, 0, c, 1){ 
				niz[cir[j].X] = cir[nxt(j)].Y;
				update(cir[j].X, niz[cir[j].X]);
			}	
			// cout << "updated: "; pri(j, 0, n, 1) cout << niz[j] << " "; cout << "\n";
		} else { 
			ll l, r, m, ans = 0;
			cin >> l >> r >> m;
			l--;
			r--; 

			if(r - l + 1 >= m * 2 - 1) {
				ans = query(l, (l + m - 1)).asc + m * query(l + m - 1, r - m + 2).sum + query(r - m + 2, r + 1).dsc; 
				// cout << l << " / " << l + m - 2 << " = " << query(l, (l + m - 1)).asc << "\n";
			} else { 
				ll mx_l = r - m + 1;
				ll mx_r = l + m - 1;
				ll mx = r - mx_r + 1;
				ans = query(l, mx_l).asc + mx * query(mx_l, mx_r + 1).sum + query(mx_r + 1, r + 1).dsc;
				//cout << mx_l << " --- " << mx_r + 1 << " = " << query(mx_l, mx_r + 1).dsc << "\n";
			}
			cout << ans << "\n";
		}

	}
	return 0;
}

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