oj.uz

Submission #475455

# Submission time Handle Problem Language Result Execution time Memory
475455 2021-09-22T14:22:51 Z GioChkhaidze Addk (eJOI21_addk) C++14
100 / 100
 161 ms 7736 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int N = 1e5 + 5;

int n, k, q, typ;
int a[N], b[N], c[N], A[N];
ll G[2 * N][4];

void upd(int x, ll dl) {
	while (x <= 100000) {
		G[x][typ] += dl;
		x += (x & -x);
	}
}

ll get(int x) {
	ll res = 0;
	while (x > 0) {
		res += G[x][typ];
		x -= (x & -x);
	}
	return res;
}

main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		typ = 0, upd(i, a[i]);
		typ = 1, upd(i, 1ll * a[i] * i);
	}
	
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		int t;
		cin >> t;
		if (t == 1) {
			for (int j = 0; j < k; ++j) {
				cin >> b[j];
				A[b[j]] = a[b[j]];
			}
			
			for (int j = 0; j < k; ++j) {
				int id = b[j], idn = b[(j + 1) % k];
				typ = 0, upd(id, -a[id]);
				typ = 1, upd(id, -a[id] * id);
				a[b[j]] = A[idn];
				typ = 1, upd(id, a[id] * id);
				typ = 0, upd(id, a[id]);
			}
		}
			else
		if (t == 2) {
			int l, r, m;
			cin >> l >> r >> m;
			int L = min(l + m - 1, r - m + 1);
			int R = max(l + m - 1, r - m + 1);
			int M = L - l + 1;
			
			ll ansL = 0, ansM = 0, ansR = 0;
			
			if (L <= R) {
				typ = 0, ansM = (get(R) - get(L - 1)) * M; // correct
			}
			
			typ = 1, ansL = get(L - 1) - get(l - 1);
			typ = 0, ansL -= (get(L - 1) - get(l - 1)) * (l - 1); // correct
			
			typ = 0, ansR = (get(r) - get(R)) * (r + 1); // correct
			typ = 1, ansR -= get(r) - get(R);
			
			/*
			cout << L << " "  << M << " " << R << "\n";
			cout << ansL << " " << ansM << " " << ansR << "\n";
			*/
			cout << ansL + ansM + ansR << "\n";
		}
	}
	
	return 0;
}

Compilation message

Main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main() {
      | ^~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 5 ms 676 KB Output is correct
7 Correct 5 ms 812 KB Output is correct
8 Correct 6 ms 844 KB Output is correct
9 Correct 8 ms 1132 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1484 KB Output is correct
2 Correct 33 ms 2568 KB Output is correct
3 Correct 35 ms 3544 KB Output is correct
4 Correct 70 ms 5744 KB Output is correct
5 Correct 92 ms 7448 KB Output is correct
6 Correct 80 ms 7296 KB Output is correct
7 Correct 94 ms 7308 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3144 KB Output is correct
2 Correct 83 ms 6120 KB Output is correct
3 Correct 161 ms 7736 KB Output is correct
4 Correct 118 ms 7480 KB Output is correct