Submission #866185

# Submission time Handle Problem Language Result Execution time Memory
866185 2023-10-25T14:48:29 Z TAhmed33 Izbori (COCI22_izbori) C++
25 / 110
103 ms 7372 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
int arr[MAXN], n;
vector <int> occ[MAXN];
vector <int> d;
struct bit { 
	int tree[2 * MAXN + 25] = {};
	void add (int pos, int val) {
		for  (; pos < 2 * MAXN + 25; pos += pos & (-pos)) tree[pos] += val;
	}
	ll get (int pos) {
		ll sum = 0; for (; pos; pos -= pos & (-pos)) sum += tree[pos];
		return sum;
	}
};
ll solve1 (int x) {
	int a[n + 1] = {}; bit cur;
	for (int i = 1; i <= n; i++) {
		a[i] = -1;
	}
	for (auto i : occ[x]) a[i] = 1;
	cur.add(MAXN, 1); 
	ll ret = 0;
	for (int i = 1; i <= n; i++) {
		a[i] += a[i - 1];
		ret += cur.get(a[i] - 1 + MAXN);
		cur.add(a[i] + MAXN, 1);
	}
	return ret;
}
ll solve2 (int x) {
	return solve1(x);
}
int main () {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		d.push_back(arr[i]);
	}
	sort(d.begin(), d.end()); d.resize(unique(d.begin(), d.end()) - d.begin());
	for (int i = 1; i <= n; i++) arr[i] = lower_bound(d.begin(), d.end(), arr[i]) - d.begin();
	for (int i = 1; i <= n; i++) {
		occ[arr[i]].push_back(i);
	}
	ll sum = 0;
	int x = sqrt(n); while (x * x < n) x++; while (x * x > n) x--;
	for (int i = 0; i < n; i++) {
		if (occ[i].size() > x) sum += solve1(i);
		else sum += solve2(i);
	}
	cout << sum << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   if (occ[i].size() > x) sum += solve1(i);
      |       ~~~~~~~~~~~~~~^~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 8 ms 3572 KB Output is correct
5 Correct 8 ms 3676 KB Output is correct
6 Correct 7 ms 3420 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 8 ms 3572 KB Output is correct
5 Correct 8 ms 3676 KB Output is correct
6 Correct 7 ms 3420 KB Output is correct
7 Correct 29 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 99 ms 3612 KB Output is correct
10 Correct 96 ms 3420 KB Output is correct
11 Correct 96 ms 3420 KB Output is correct
12 Correct 97 ms 3608 KB Output is correct
13 Correct 99 ms 3596 KB Output is correct
14 Correct 99 ms 3416 KB Output is correct
15 Correct 96 ms 3612 KB Output is correct
16 Correct 103 ms 3620 KB Output is correct
17 Correct 95 ms 3416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 8 ms 3572 KB Output is correct
5 Correct 8 ms 3676 KB Output is correct
6 Correct 7 ms 3420 KB Output is correct
7 Correct 29 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 99 ms 3612 KB Output is correct
10 Correct 96 ms 3420 KB Output is correct
11 Correct 96 ms 3420 KB Output is correct
12 Correct 97 ms 3608 KB Output is correct
13 Correct 99 ms 3596 KB Output is correct
14 Correct 99 ms 3416 KB Output is correct
15 Correct 96 ms 3612 KB Output is correct
16 Correct 103 ms 3620 KB Output is correct
17 Correct 95 ms 3416 KB Output is correct
18 Runtime error 14 ms 7372 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -