oj.uz

Submission #866186

# Submission time Handle Problem Language Result Execution time Memory
866186 2023-10-25T14:48:59 Z TAhmed33 Izbori (COCI22_izbori) C++
25 / 110
 3000 ms 9164 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 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);
      |       ~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 13 ms 6708 KB Output is correct
4 Correct 13 ms 6488 KB Output is correct
5 Correct 13 ms 6492 KB Output is correct
6 Correct 13 ms 6488 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 13 ms 6708 KB Output is correct
4 Correct 13 ms 6488 KB Output is correct
5 Correct 13 ms 6492 KB Output is correct
6 Correct 13 ms 6488 KB Output is correct
7 Correct 48 ms 6492 KB Output is correct
8 Correct 6 ms 6492 KB Output is correct
9 Correct 163 ms 6724 KB Output is correct
10 Correct 154 ms 6492 KB Output is correct
11 Correct 156 ms 6748 KB Output is correct
12 Correct 154 ms 6496 KB Output is correct
13 Correct 158 ms 6488 KB Output is correct
14 Correct 147 ms 6720 KB Output is correct
15 Correct 146 ms 6492 KB Output is correct
16 Correct 142 ms 6488 KB Output is correct
17 Correct 172 ms 6716 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 9164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 13 ms 6708 KB Output is correct
4 Correct 13 ms 6488 KB Output is correct
5 Correct 13 ms 6492 KB Output is correct
6 Correct 13 ms 6488 KB Output is correct
7 Correct 48 ms 6492 KB Output is correct
8 Correct 6 ms 6492 KB Output is correct
9 Correct 163 ms 6724 KB Output is correct
10 Correct 154 ms 6492 KB Output is correct
11 Correct 156 ms 6748 KB Output is correct
12 Correct 154 ms 6496 KB Output is correct
13 Correct 158 ms 6488 KB Output is correct
14 Correct 147 ms 6720 KB Output is correct
15 Correct 146 ms 6492 KB Output is correct
16 Correct 142 ms 6488 KB Output is correct
17 Correct 172 ms 6716 KB Output is correct
18 Execution timed out 3032 ms 9164 KB Time limit exceeded
19 Halted 0 ms 0 KB -