oj.uz

Submission #813326

# Submission time Handle Problem Language Result Execution time Memory
813326 2023-08-07T16:03:11 Z enerelt14 Diversity (CEOI21_diversity) C++14
4 / 100
 48 ms 31416 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

#define ff first
#define ss second
#define ll long long

const int MX = 3e5 + 5;
const int MX1 = 5e4 + 5;
const int B = 1341;

int N, Q;
int a[MX], num[MX], l[MX], r[MX];
int ans[MX1];
pair<pair<int, int>, pair<int, int> > q[MX1];
ll val;

struct T{
	ll sum, left_sum, right_sum;
	T() {
		sum = left_sum = right_sum = 0;
	}
} tree[4 * MX];

void show(T x) {
	cout << x.left_sum << " " << x.right_sum << " " << x.sum << "\n";
}

void update(int id, int l, int r, int pos, int x) {
	if(l > pos || pos > r) return;
	tree[id].sum += x;
	tree[id].left_sum += x * (pos - l + 1);
	tree[id].right_sum += x * (r - pos + 1);
	if(l == r) return;
	int mid = (l + r) / 2;
	update(id * 2 + 1, l, mid, pos, x);
	update(id * 2 + 2, mid + 1, r, pos, x);
}

T query(int id, int l, int r, int L, int R) {
	T res;
	if(L > r || l > R) return res;
	if(L <= l && r <= R) return tree[id];
	int mid = (l + r) / 2;
	if(L > mid) return query(id * 2 + 2, mid + 1, r, L, R);
	if(R <= mid) return query(id * 2 + 1, l, mid, L, R);
	T x = query(id * 2 + 1, l, mid, L, R), y = query(id * 2 + 2, mid + 1, r, L, R);
	res.sum = x.sum + y.sum;
	res.left_sum = x.left_sum + y.left_sum + y.sum * (mid - L + 1);
	res.right_sum = x.right_sum + y.right_sum + x.sum * (R - mid);
	return res;
}

int prv(int x) {
	if(x <= (N - 1) / 2) return N - x;
	else return N - x - 1;
}

int nxt(int x) {
	if(x <= N / 2) return N - x - 1;
	else return N - x;
}

void add(int x) {
	num[x]++;
	l[num[x]] = r[num[x] - 1];
	if(r[num[x]] == -1) r[num[x]] = l[num[x]];
	if(r[num[x] - 1] == l[num[x] - 1]) r[num[x] - 1] = l[num[x] - 1] = -1;
	else r[num[x] - 1] = prv(r[num[x] - 1]);
	update(0, 0, N - 1, l[num[x]], 1);
	T y, z;
	if(l[num[x]] != 0) y = query(0, 0, N - 1, 0, l[num[x]] - 1);
	if(l[num[x]] != N - 1) z = query(0, 0, N - 1, l[num[x]] + 1, N - 1);
	val += y.right_sum + y.sum + z.left_sum + z.sum;
	val += num[x];
	// show(y);
	// show(z);
	// cout << val << "\n---------\n";
}

void remove(int x) {
	num[x]--;
	r[num[x]] = l[num[x] + 1];
	if(l[num[x]] == -1) l[num[x]] = r[num[x]];
	if(r[num[x] + 1] == l[num[x] + 1]) r[num[x] + 1] = l[num[x] + 1] = -1;
	else l[num[x] + 1] = nxt(l[num[x] + 1]);
	update(0, 0, N - 1, r[num[x]], -1);
	T y, z;
	if(r[num[x]] != 0) y = query(0, 0, N - 1, 0, r[num[x]] - 1);
	if(r[num[x]] != N - 1) z = query(0, 0, N - 1, r[num[x]] + 1, N - 1);
	val -= y.right_sum + y.sum + z.left_sum + z.sum;
	val -= (num[x] + 1);
}

int main() {
	memset(l, -1, sizeof(l));
	memset(r, -1, sizeof(r));
	cin >> N >> Q;
	l[0] = 0;
	r[0] = N / 2;
	for(int i = 0; i < N; i++) cin >> a[i];
	for(int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		q[i] = {{l / B, r}, {l, i}};
	}
	sort(q, q + Q);
	for(int i = 0; i < Q; i++) {
		if(i == 0) {
			for(int j = 0; j <= q[i].ff.ss; j++) add(a[j]);
			for(int j = 0; j < q[i].ss.ff; j++) remove(a[j]);
			ans[q[i].ss.ss] = val;
			continue;
		}
		for(int j = q[i - 1].ff.ss + 1; j <= q[i].ff.ss; j++) add(a[j]);
		for(int j = q[i - 1].ff.ss; j > q[i].ff.ss; j--) remove(a[j]);
		for(int j = q[i - 1].ss.ff; j < q[i].ss.ff; j++) remove(a[j]);
		for(int j = q[i - 1].ss.ff - 1; j >= q[i].ss.ff; j--) add(a[j]);
		ans[q[i].ss.ss] = val;
	}
	for(int i = 0; i < Q; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30812 KB Output is correct
2 Correct 11 ms 30764 KB Output is correct
3 Correct 11 ms 30820 KB Output is correct
4 Correct 11 ms 30804 KB Output is correct
5 Correct 13 ms 30828 KB Output is correct
6 Correct 12 ms 30828 KB Output is correct
7 Correct 13 ms 30852 KB Output is correct
8 Correct 12 ms 30824 KB Output is correct
9 Correct 12 ms 30804 KB Output is correct
10 Correct 11 ms 30840 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 11 ms 30744 KB Output is correct
3 Correct 13 ms 30912 KB Output is correct
4 Incorrect 48 ms 31416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 11 ms 30744 KB Output is correct
3 Correct 13 ms 30912 KB Output is correct
4 Incorrect 48 ms 31416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 11 ms 30744 KB Output is correct
3 Correct 13 ms 30912 KB Output is correct
4 Incorrect 48 ms 31416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30812 KB Output is correct
2 Correct 11 ms 30764 KB Output is correct
3 Correct 11 ms 30820 KB Output is correct
4 Correct 11 ms 30804 KB Output is correct
5 Correct 13 ms 30828 KB Output is correct
6 Correct 12 ms 30828 KB Output is correct
7 Correct 13 ms 30852 KB Output is correct
8 Correct 12 ms 30824 KB Output is correct
9 Correct 12 ms 30804 KB Output is correct
10 Correct 11 ms 30840 KB Output is correct
11 Correct 11 ms 30804 KB Output is correct
12 Correct 11 ms 30744 KB Output is correct
13 Correct 13 ms 30912 KB Output is correct
14 Incorrect 48 ms 31416 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30812 KB Output is correct
2 Correct 11 ms 30764 KB Output is correct
3 Correct 11 ms 30820 KB Output is correct
4 Correct 11 ms 30804 KB Output is correct
5 Correct 13 ms 30828 KB Output is correct
6 Correct 12 ms 30828 KB Output is correct
7 Correct 13 ms 30852 KB Output is correct
8 Correct 12 ms 30824 KB Output is correct
9 Correct 12 ms 30804 KB Output is correct
10 Correct 11 ms 30840 KB Output is correct
11 Correct 11 ms 30804 KB Output is correct
12 Correct 11 ms 30744 KB Output is correct
13 Correct 13 ms 30912 KB Output is correct
14 Incorrect 48 ms 31416 KB Output isn't correct
15 Halted 0 ms 0 KB -