oj.uz

답안 #711068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711068 2023-03-16T08:02:32 Z DEQK Izbori (COCI22_izbori) C++17
110 / 110
 595 ms 30992 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(a) ((int) a.size())
#define ls u << 1
#define rs u << 1 | 1
const int N = 5e5 + 15;
const int M = 4e6 + 19;
int n, k, a[N], cur = 1, b[N];
vector<int> pos[N];
ll add[M], tr[M];
int ver[M], cnt[M];
inline void push(int u, int l, int r) {
	if(ver[u] != cur) {
		tr[u] = cnt[u] = add[u] = 0;
		ver[u] = cur;
	}
	int len = r - l + 1;
	tr[u] += add[u] * len + (len + 1) * len / 2 * cnt[u];
	if(l != r) {
		int m = (l + r) / 2;
		if(ver[ls] != cur) {
			ver[ls] = cur;
			tr[ls] = cnt[ls] = add[ls] = 0;
		}
		if(ver[rs] != cur) {
			ver[rs] = cur;
			tr[rs] = cnt[rs] = add[rs] = 0;
		}
		add[ls] += add[u];
		add[rs] += add[u] + (m - l + 1) * cnt[u];
		cnt[ls] += cnt[u];
		cnt[rs] += cnt[u];
	}
	add[u] = cnt[u] = 0;
	return;
}
void upd(int ql, int qr, int u = 1, int l = 0, int r = 2 * n) {
	push(u, l, r);
	if(ql > r || l > qr) return;
	if(ql <= l && r <= qr) {
		add[u] += l - ql;
		cnt[u]++;
		push(u, l, r);
		return;
	}
	int m = (l + r) >> 1;
	upd(ql, qr, ls, l, m);
	upd(ql, qr, rs, m + 1, r);
	tr[u] = tr[ls] + tr[rs];
}
void upd2(int ql, int qr, int x, int u = 1, int l = 0, int r = 2 * n) {
	if(ql > r || l > qr) return;
	push(u, l, r);
	if(ql <= l && r <= qr) {
		add[u] += x;
		push(u, l, r);
		return;
	}
	int m = (l + r) >> 1;
	upd2(ql, qr, x, ls, l, m);
	upd2(ql, qr, x, rs, m + 1, r);
	tr[u] = tr[ls] + tr[rs];
}
ll get(int ql, int qr, int u = 1, int l = 0, int r = 2 * n) {
	if(ql > r || l > qr || ql > qr) return 0;
	push(u, l, r);	
	if(ql <= l && r <= qr) return tr[u];
	int m = (l + r) >> 1;
	return get(ql, qr, ls, l, m) + get(ql, qr, rs, m + 1, r); 
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++) {
		a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
		pos[a[i]].pb(i);
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		if(!sz(pos[i])) continue;
		cur = i;
		upd(-pos[i][0] + 1 + n, n);
		upd2(n + 1, n + n, pos[i][0]);
		for(int j = 0; j < sz(pos[i]); j++) {
			int cnt = j + 1;
			int ps = pos[i][j];
			int nt = n + 1;
			if(j != sz(pos[i]) - 1) {
				nt = pos[i][j + 1]; 
			}
			ans += get((cnt << 1) - nt + n, (cnt << 1) - ps + n - 1);
			upd((cnt << 1) - nt + n + 1, (cnt << 1) - ps + n);
			upd2((cnt << 1) - ps + n + 1, (n << 1), nt - ps);
		}
	}
	cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 10 ms 12244 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 9 ms 12216 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 9 ms 12236 KB Output is correct
14 Correct 9 ms 12220 KB Output is correct
15 Correct 10 ms 12292 KB Output is correct
16 Correct 9 ms 12244 KB Output is correct
17 Correct 10 ms 12232 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 14208 KB Output is correct
2 Correct 194 ms 14992 KB Output is correct
3 Correct 118 ms 13880 KB Output is correct
4 Correct 205 ms 14964 KB Output is correct
5 Correct 206 ms 15200 KB Output is correct
6 Correct 223 ms 15296 KB Output is correct
7 Correct 214 ms 15316 KB Output is correct
8 Correct 226 ms 15396 KB Output is correct
9 Correct 213 ms 15292 KB Output is correct
10 Correct 210 ms 15320 KB Output is correct
11 Correct 227 ms 27356 KB Output is correct

Subtask #4
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 10 ms 12244 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 9 ms 12216 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 9 ms 12236 KB Output is correct
14 Correct 9 ms 12220 KB Output is correct
15 Correct 10 ms 12292 KB Output is correct
16 Correct 9 ms 12244 KB Output is correct
17 Correct 10 ms 12232 KB Output is correct
18 Correct 141 ms 14208 KB Output is correct
19 Correct 194 ms 14992 KB Output is correct
20 Correct 118 ms 13880 KB Output is correct
21 Correct 205 ms 14964 KB Output is correct
22 Correct 206 ms 15200 KB Output is correct
23 Correct 223 ms 15296 KB Output is correct
24 Correct 214 ms 15316 KB Output is correct
25 Correct 226 ms 15396 KB Output is correct
26 Correct 213 ms 15292 KB Output is correct
27 Correct 210 ms 15320 KB Output is correct
28 Correct 227 ms 27356 KB Output is correct
29 Correct 232 ms 28924 KB Output is correct
30 Correct 101 ms 16908 KB Output is correct
31 Correct 230 ms 21456 KB Output is correct
32 Correct 595 ms 30992 KB Output is correct
33 Correct 242 ms 21636 KB Output is correct
34 Correct 253 ms 21836 KB Output is correct
35 Correct 172 ms 17592 KB Output is correct
36 Correct 103 ms 16636 KB Output is correct
37 Correct 111 ms 17016 KB Output is correct
38 Correct 256 ms 22692 KB Output is correct
39 Correct 242 ms 22580 KB Output is correct
40 Correct 247 ms 22716 KB Output is correct
41 Correct 259 ms 22600 KB Output is correct
42 Correct 279 ms 22788 KB Output is correct
43 Correct 282 ms 27228 KB Output is correct
44 Correct 285 ms 27236 KB Output is correct
45 Correct 272 ms 27140 KB Output is correct
46 Correct 286 ms 27160 KB Output is correct
47 Correct 279 ms 27200 KB Output is correct
48 Correct 482 ms 27664 KB Output is correct
49 Correct 375 ms 27724 KB Output is correct
50 Correct 371 ms 27832 KB Output is correct
51 Correct 335 ms 27744 KB Output is correct
52 Correct 358 ms 27704 KB Output is correct
53 Correct 355 ms 27716 KB Output is correct
54 Correct 376 ms 27644 KB Output is correct