oj.uz

답안 #814226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814226 2023-08-08T06:27:23 Z enerelt14 Diversity (CEOI21_diversity) C++14
4 / 100
 68 ms 10888 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 = 500;

int N, Q;
int a[MX], num[MX], l[MX], r[MX];
ll 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[MX];

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];
}

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() {
	ios::sync_with_stdio(0);cin.tie(0);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9632 KB Output is correct
7 Correct 4 ms 9732 KB Output is correct
8 Correct 5 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 6 ms 9736 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct
4 Correct 41 ms 10296 KB Output is correct
5 Incorrect 68 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 6 ms 9736 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct
4 Correct 41 ms 10296 KB Output is correct
5 Incorrect 68 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 6 ms 9736 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct
4 Correct 41 ms 10296 KB Output is correct
5 Incorrect 68 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9632 KB Output is correct
7 Correct 4 ms 9732 KB Output is correct
8 Correct 5 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9732 KB Output is correct
12 Correct 6 ms 9736 KB Output is correct
13 Correct 9 ms 9684 KB Output is correct
14 Correct 41 ms 10296 KB Output is correct
15 Incorrect 68 ms 10888 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9632 KB Output is correct
7 Correct 4 ms 9732 KB Output is correct
8 Correct 5 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9732 KB Output is correct
12 Correct 6 ms 9736 KB Output is correct
13 Correct 9 ms 9684 KB Output is correct
14 Correct 41 ms 10296 KB Output is correct
15 Incorrect 68 ms 10888 KB Output isn't correct
16 Halted 0 ms 0 KB -