Submission #586745

#	Time	Username	Problem	Language	Result	Execution time	Memory
586745		algorithm16	Addk (eJOI21_addk)	C++14	100 / 100	443 ms	12200 KiB

Main

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn = 1e5 + 7;

struct tourn {
	ll sum, psum, ssum, dub;
} t[maxn * 4];

int n, q, k, ofs = 1;
int ar[maxn], sw[17];

tourn calc(tourn t1, tourn t2) {
	tourn e;
	e.sum = t1.sum + t2.sum;
	e.psum = t1.psum + t2.psum + t2.sum * t1.dub;
	e.ssum = t1.ssum + t2.ssum + t1.sum * t2.dub;
	e.dub = t1.dub + t2.dub;
	return e;
}

void Update(int x, int val) {
	x += ofs;
	t[x].sum = val;
	t[x].psum = val;
	t[x].ssum = val;
	t[x].dub = 1;
	while (x >>= 1) {
		t[x] = calc(t[x*2], t[x*2+1]);
	}
}

tourn Query(int x, int a, int b, int lo, int hi) {
	//cout << x << " <- X, " << lo << " " << hi << "\n";
	if (hi < a || lo > b) {
		//cout << "1!\n";
		return {0, 0, 0, 0};
	}
	if (lo >= a && hi <= b) {
		//cout << "2!\n";
		return t[x];
	}
	tourn d1, d2;
	d1 = Query(x*2, a, b, lo, (lo + hi) / 2);
	d2 = Query(x*2+1, a, b, (lo + hi) / 2 + 1, hi);
	//cout << "3!\n";
	//cout << x << " " << calc(d1, d2).sum << " - " << calc(d1, d2).psum << " - " << calc(d1, d2).ssum << " - " << calc(d1, d2).dub << "\n";
	return calc(d1, d2);
}

int main () {
	cin >> n >> k;
	
	while (ofs < n) ofs <<= 1;
	
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
		Update(i, ar[i]);
	}
	/*
	for (int i = 1; i < ofs*2; i++) {
		cout << i << " " << t[i].sum << " " << t[i].psum << " " << t[i].ssum << " " << t[i].dub << "\n";
	}*/
	
	cin >> q;
	
	for (int i = 0; i < q; i++) {
		int ot; cin >> ot;
		if (ot == 1) {
			int tmp;
			for (int j = 0; j < k; j++) {
				cin >> sw[j]; --sw[j];
				if (j) {
					ar[sw[j-1]] = ar[sw[j]];
					Update(sw[j-1], ar[sw[j-1]]);
				}
				else {
					tmp = ar[sw[j]];
				}
			}
			ar[sw[k-1]] = tmp;
			Update(sw[k-1], tmp);
		}
		else {
			int l, r, m;
			cin >> l >> r >> m; --l; --r;
			int p1 = l + m - 1, p2 = r - m + 1;
			tourn d1 = Query(1, l, p1, 0, ofs-1);
			tourn d2 = Query(1, p2, r, 0, ofs-1);
			int pz = 1;
			if (p2 <= p1) {
				swap(p2, p1);
				pz = -1;
				p1--;
				p2++;
			}
			tourn d3;
			if (p1 == p2-1) d3 = {0, 0, 0, 0};
			else {
				p1++;
				p2--;
				d3 = Query(1, p1, p2, 0, ofs-1);
			}
			//cout << d1.psum << " " << d2.ssum << " " << d3.sum << "\n";
			cout << d1.psum + d2.ssum + d3.sum * pz * m << "\n";
		}
	}
	
	return 0;
}









			/*if (le < m * 2 - 1) {
				tourn d1 = Query(1, l, l + ra, 0, ofs);
				tourn d2 = Query(1, r - ra, r, 0, ofs);
				if (r - l - 2 * ra > 1) {
					tourn d3 = Query(1, l + ra + 1, r , 0, ofs);
					ll res = d1.psum + d2.ssum + d3.sum;
					cout << res << "\n";
				}
				else {
					ll res = d1.psum + d2.ssum;
					cout << res << "\n";
				}
			}
			else {
				tourn d1 = Query(1, l, l + m - 1)
				if (r - l - 2 * ra > 1) {
					tourn d3 = Query(1, l + ra + 1, r , 0, ofs);
					ll res = d1.psum + d2.ssum + d3.sum * (ra + 1);
					cout << res << "\n";
				}
				else {
					ll res = d1.psum + d2.ssum;
					cout << res << "\n";
				}
			}*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:85:10: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |    Update(sw[k-1], tmp);
      |    ~~~~~~^~~~~~~~~~~~~~

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