oj.uz

Submission #527961

# Submission time Handle Problem Language Result Execution time Memory
527961 2022-02-18T20:51:15 Z 1ne Izbori (COCI22_izbori) C++14
40 / 110
 3000 ms 10432 KB 
#include<iostream>
#include<algorithm>
#include<functional>
#include<numeric>
#include<vector>
#include<utility>
#include<map>
#include<set>
using namespace std;
long long merge(int left, int mid, int right, vector<int64_t>& arr) {
	vector<int64_t>temp;
	int i = left, j = mid + 1;
	long long ans = 0;
	while (i <= mid && j <= right) {
		if (arr[i] >= arr[j]) {
			temp.push_back(arr[i]);
			++i;
		}
		else {
			temp.push_back(arr[j]);
			++j;
			ans += (mid - i + 1);
		}
	}
	while (i <= mid) {
		temp.push_back(arr[i]);
		++i;
	}
	while (j <= right) {
		temp.push_back(arr[j]);
		++j;
	}
	for (auto x : temp) {
		arr[left] = x;
		++left;
	}
	return ans;
}
long long mergesort(int left, int right, vector<int64_t>& arr) {
	int mid = (left + right) >> 1;
	if (left >= right)return 0;
	long long ans = 0;
	ans += mergesort(left, mid, arr);
	ans += mergesort(mid + 1, right, arr);
	ans += merge(left, mid, right, arr);
	return ans;
}
int main() {
	int n;cin >> n;
	vector<int>arr(n);
	bool ok = true;
	for (int i = 0;i < n;++i) {
		cin >> arr[i];
		if (arr[i] > 2)ok = false;
		arr[i]--;
	}
	if (ok) {
		int64_t ans = 0;
		vector<int64_t>freq(n+1, 0);
		for (int i = 0;i < n;++i) {
			if (arr[i] == 0) {
				freq[i+1]++;
			}
			else freq[i+1]--;
			freq[i + 1] += freq[i];
		}
		ans += mergesort(0, n, freq);
		for (int i = 0;i <= n;++i) {
			freq[i] = 0;
		}
		for (int i = 0;i < n;++i) {
			if (arr[i] == 0) {
				freq[i+1]--;
			}
			else freq[i+1]++;
			freq[i+1] += freq[i];
		}
		ans += mergesort(0, n, freq);
		cout << ans << '\n';
		return 0;
	}
	int64_t ans = n;
	arr.push_back(-1);
	for (int i = 2;i <= n;++i) {
		map<int, int>freq;
		multiset < pair<int, int>, greater<pair<int, int>>>mp;
		for (int j = 0;j < i;++j) {
			freq[arr[j]]++;
		}
		for (auto x : freq) {
			mp.insert({ x.second,x.first });
		}
		for (int j = 0;j <= n - i;++j) {
			auto x = *mp.begin();
			if (x.first > i / 2) {
				ans++;
			}
			mp.erase({ freq[arr[j]],arr[j] });
			freq[arr[j]]--;
			mp.insert({ freq[arr[j]],arr[j] });
			freq[arr[j + i]]++;
			mp.insert({ freq[arr[j + i]],arr[j + i] });
		}
	}
	cout << ans << '\n';

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 17 ms 304 KB Output is correct
4 Correct 15 ms 288 KB Output is correct
5 Correct 15 ms 204 KB Output is correct
6 Correct 7 ms 292 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 17 ms 304 KB Output is correct
4 Correct 15 ms 288 KB Output is correct
5 Correct 15 ms 204 KB Output is correct
6 Correct 7 ms 292 KB Output is correct
7 Correct 420 ms 368 KB Output is correct
8 Correct 4 ms 204 KB Output is correct
9 Correct 856 ms 368 KB Output is correct
10 Correct 836 ms 372 KB Output is correct
11 Correct 865 ms 372 KB Output is correct
12 Correct 822 ms 368 KB Output is correct
13 Correct 819 ms 368 KB Output is correct
14 Correct 823 ms 372 KB Output is correct
15 Correct 822 ms 364 KB Output is correct
16 Correct 876 ms 368 KB Output is correct
17 Correct 305 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4892 KB Output is correct
2 Correct 82 ms 5724 KB Output is correct
3 Correct 52 ms 3304 KB Output is correct
4 Correct 93 ms 5880 KB Output is correct
5 Correct 89 ms 6004 KB Output is correct
6 Correct 92 ms 6248 KB Output is correct
7 Correct 93 ms 6180 KB Output is correct
8 Correct 100 ms 6188 KB Output is correct
9 Correct 103 ms 6176 KB Output is correct
10 Correct 99 ms 6372 KB Output is correct
11 Correct 81 ms 6180 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 17 ms 304 KB Output is correct
4 Correct 15 ms 288 KB Output is correct
5 Correct 15 ms 204 KB Output is correct
6 Correct 7 ms 292 KB Output is correct
7 Correct 420 ms 368 KB Output is correct
8 Correct 4 ms 204 KB Output is correct
9 Correct 856 ms 368 KB Output is correct
10 Correct 836 ms 372 KB Output is correct
11 Correct 865 ms 372 KB Output is correct
12 Correct 822 ms 368 KB Output is correct
13 Correct 819 ms 368 KB Output is correct
14 Correct 823 ms 372 KB Output is correct
15 Correct 822 ms 364 KB Output is correct
16 Correct 876 ms 368 KB Output is correct
17 Correct 305 ms 332 KB Output is correct
18 Correct 61 ms 4892 KB Output is correct
19 Correct 82 ms 5724 KB Output is correct
20 Correct 52 ms 3304 KB Output is correct
21 Correct 93 ms 5880 KB Output is correct
22 Correct 89 ms 6004 KB Output is correct
23 Correct 92 ms 6248 KB Output is correct
24 Correct 93 ms 6180 KB Output is correct
25 Correct 100 ms 6188 KB Output is correct
26 Correct 103 ms 6176 KB Output is correct
27 Correct 99 ms 6372 KB Output is correct
28 Correct 81 ms 6180 KB Output is correct
29 Execution timed out 3063 ms 10432 KB Time limit exceeded
30 Halted 0 ms 0 KB -