oj.uz

Submission #586745

# Submission time Handle Problem Language Result Execution time Memory
586745 2022-06-30T15:50:06 Z algorithm16 Addk (eJOI21_addk) C++14
100 / 100
 443 ms 12200 KB 
#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

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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 324 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 11 ms 596 KB Output is correct
5 Correct 16 ms 716 KB Output is correct
6 Correct 16 ms 816 KB Output is correct
7 Correct 22 ms 1016 KB Output is correct
8 Correct 23 ms 980 KB Output is correct
9 Correct 36 ms 1236 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2364 KB Output is correct
2 Correct 104 ms 3372 KB Output is correct
3 Correct 160 ms 4496 KB Output is correct
4 Correct 294 ms 7764 KB Output is correct
5 Correct 387 ms 10888 KB Output is correct
6 Correct 443 ms 10676 KB Output is correct
7 Correct 360 ms 10680 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 5988 KB Output is correct
2 Correct 320 ms 9100 KB Output is correct
3 Correct 430 ms 12200 KB Output is correct
4 Correct 403 ms 11184 KB Output is correct