oj.uz

답안 #637052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637052 2022-08-31T11:07:04 Z Tsovak Addk (eJOI21_addk) C++17
100 / 100
 237 ms 14604 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()

#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ft front
#define bk back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

ll gcd(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) {
		return false;
	}
	for (ll i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			return false;
		}
	}
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrt(a));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrt(a));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
		}
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
			ans %= mod;
		}
		b >>= 1;
		a *= a;
		a %= mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) {
		ans *= ll(i);
	}
	return ans;
}

ll factorial_by_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) {
		ans *= ll(i);
		ans %= mod;
	}
	return ans;
}

// -------------------- Solution -------------------- //

struct node
{
	ll sum;
	ll sum1;
	ll sum2;
	ll len;
};

const int N = 100005;
ll a[N];
int n;

vector<int> v;

node t[N * 4];

node merge(node x, node y)
{
	node res;

	res.sum = x.sum + y.sum;
	res.sum1 = x.sum1 + ll(x.len) * y.sum + y.sum1;
	res.sum2 = y.sum2 + ll(y.len) * x.sum + x.sum2;
	res.len = x.len + y.len;

	return res;
}

void bld(int tl, int tr, int pos)
{
	if (tl == tr) {
		t[pos].sum = t[pos].sum1 = t[pos].sum2 = a[tl];
		t[pos].len = 1;
		return;
	}

	int m = (tl + tr) / 2;

	bld(tl, m, pos * 2);
	bld(m + 1, tr, pos * 2 + 1);

	t[pos] = merge(t[pos * 2], t[pos * 2 + 1]);

	return;
}

void upd(int tl, int tr, int ind, ll x, int pos)
{
	if (tl == tr) {
		t[pos].sum = t[pos].sum1 = t[pos].sum2 = x;
		return;
	}

	int m = (tl + tr) / 2;

	if (ind <= m) {
		upd(tl, m, ind, x, pos * 2);
	}
	else {
		upd(m + 1, tr, ind, x, pos * 2 + 1);
	}

	t[pos] = merge(t[pos * 2], t[pos * 2 + 1]);

	return;
}

node qry(int tl, int tr, int l, int r, int pos)
{
	if (l > r) return { 0, 0, 0, 1 };

	if (tl == l && tr == r) {
		return t[pos];
	}

	int m = (tl + tr) / 2;

	if (r <= m) {
		return qry(tl, m, l, r, pos * 2);
	}
	if (l > m) {
		return qry(m + 1, tr, l, r, pos * 2 + 1);
	}

	return merge(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}

void solve()
{
	int i, j;

	int k, q;

	cin >> n >> k;

	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}

	bld(1, n, 1);

	cin >> q;

	for (i = 1; i <= q; i++) {
		int tp;
		cin >> tp;

		if (tp == 1) {
			clr(v);

			int ind;
			for (j = 1; j <= k; j++) {
				cin >> ind;
				v.pb(ind);
			}

			if (k == 1) {
				continue;
			}

			ll h = a[v[0]];

			for (j = 1; j < k; j++) {
				upd(1, n, v[j - 1], a[v[j]], 1);
				swap(a[v[j - 1]], a[v[j]]);
			}

			upd(1, n, v[k - 1], h, 1);
		}
		else {
			int l, r, m;

			cin >> l >> r >> m;
			int d = r - l + 1;

			if (d == m) {
				cout << qry(1, n, l, r, 1).sum << "\n";
			}
			else if (d <= 2 * m) {
				int x = d - m;

				cout << qry(1, n, l, l + x - 1, 1).sum1 + qry(1, n, l + x, r - x, 1).sum * ll(x + 1) + qry(1, n, r - x + 1, r, 1).sum2 << "\n";
			}
			else {
				cout << qry(1, n, l, l + m - 1, 1).sum1 + qry(1, n, l + m, r - m, 1).sum * ll(m) + qry(1, n, r - m + 1, r, 1).sum2 << "\n";
			}
		}
	}

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	//cout << db(clock()) / CLOCKS_PER_SEC << endl;

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Subtask #1
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 988 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 8 ms 1108 KB Output is correct
9 Correct 11 ms 1772 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 3196 KB Output is correct
2 Correct 37 ms 3788 KB Output is correct
3 Correct 56 ms 6252 KB Output is correct
4 Correct 93 ms 11824 KB Output is correct
5 Correct 146 ms 13184 KB Output is correct
6 Correct 131 ms 13004 KB Output is correct
7 Correct 142 ms 13068 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 7124 KB Output is correct
2 Correct 137 ms 12676 KB Output is correct
3 Correct 237 ms 14604 KB Output is correct
4 Correct 157 ms 13524 KB Output is correct