oj.uz

답안 #769001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769001 2023-06-29T04:34:30 Z vjudge1 Izbori (COCI22_izbori) C++17
110 / 110
 1746 ms 13604 KB 
#include <bits/stdc++.h>
using namespace std;

#define                   f  first
#define                   s  second
#define                  mp  make_pair
#define                next  ___next
#define                prev  ___prev
#define             MASK(i)  (1ll << (i))
#define           BIT(x, i)  (((x) >> (i)) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define               sz(x)  (int32_t)(x.size())
#define              all(x)  x.begin(), x.end()
#define           mem(f, x)  memset(f, x, sizeof(f))
#define        FOR(i, l, r)  for (int32_t i = (l); i <= (r); ++i)
#define        REP(i, l, r)  for (int32_t i = (l); i < (r); ++i)
#define       FORD(i, r, l)  for (int32_t i = (r); i >= (l); --i)
#define       REPD(i, r, l)  for (int32_t i = (r - 1); i >= (l); --i)

using ll = long long;
using ld = long double;

template<class A, class B> bool mini(A &a, const B &b) {return a > b ? (a = b, true) : false;};
template<class A, class B> bool maxi(A &a, const B &b) {return a < b ? (a = b, true) : false;};
template<class T> T Abs(const T &x) {return (x < 0 ? -x : x);}

constexpr int MOD = 1e9 + 7; // 998244353

template<class X, class Y> void add(X &x, const Y &y) {x = (x + y); if (x >= MOD) x -= MOD;}
template<class X, class Y> void sub(X &x, const Y &y) {x = (x - y); if (x < 0) x += MOD;}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/* Author: Phan */

/** END OF TEMPLATE. **/

int const mxN = 2e5 + 5, up = 2e5 + 1, S = 447;

int n;
int a[mxN];
bool light[mxN];
vector <int> s[mxN];

struct Fenwick {
	int n; int s[mxN << 1];
	Fenwick(int _n = up << 1): n(_n) {};
	void reset(void) {
		mem(s, 0);
	}
	void update(int i, int x) {
		for (; i <= n; i += (i & (-i))) {
			s[i] += x;
		}
	}
	int get(int i) {
		int res = 0;
		for (; i > 0; i -= (i & (-i))) {
			res += s[i];
		}
		return res;
	}
	void add(int i) {
		update(i, 1);
	}
	void del(int i) {
		update(i, -1);
	}
};

int32_t main(void) {
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n;
	vector <int> nen;
	FOR(i, 1, n) {
		cin >> a[i];
		nen.emplace_back(a[i]);
	}
	sort(all(nen)); nen.erase(unique(all(nen)), nen.end());
	FOR(i, 1, n) {
		a[i] = lower_bound(all(nen), a[i]) - nen.begin() + 1;
		s[a[i]].emplace_back(i);
	}
	ll res = 0;
	Fenwick bit;
	auto heavy = [&](int i) {
		bit.reset();
		bit.add(up);
		int j = 0, cur = up;
		FOR(id, 1, n) {
			if (j < sz(s[i]) && id == s[i][j]) {
				j++;
				cur++;
			} else {
				cur--;
			}
			res += bit.get(cur - 1);
			bit.add(cur);
		}
	};
	FOR(i, 1, sz(nen)) {
		if (sz(s[i]) <= S) {
			light[i] = 1;
		} else {
			heavy(i);
		}
	}
	auto process = [&](void) {
		vector <int> val;
		vector <int> cnt(sz(nen) + 2);
		FOR(i, 1, n) {
			int len = min(n - i + 1, 2 * S), mx = 0;
			FOR(j, 1, len) {
				int r = i + j - 1;
				if (light[a[r]] == 0) continue;
				val.emplace_back(a[r]);
				cnt[a[r]]++;
				maxi(mx, cnt[a[r]]);
				if (mx * 2 > j) res++;
			}
			for (int &x : val) cnt[x] = 0;
			val.clear();
		}
	};
	process();
	cout << res;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6592 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6588 KB Output is correct
5 Correct 3 ms 6496 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6592 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6588 KB Output is correct
5 Correct 3 ms 6496 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 5 ms 6544 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 7 ms 6656 KB Output is correct
10 Correct 7 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6600 KB Output is correct
13 Correct 7 ms 6612 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct
15 Correct 7 ms 6664 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 5 ms 6612 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 8956 KB Output is correct
2 Correct 118 ms 9688 KB Output is correct
3 Correct 70 ms 8396 KB Output is correct
4 Correct 123 ms 9680 KB Output is correct
5 Correct 128 ms 9660 KB Output is correct
6 Correct 143 ms 9724 KB Output is correct
7 Correct 135 ms 9808 KB Output is correct
8 Correct 135 ms 9936 KB Output is correct
9 Correct 137 ms 9808 KB Output is correct
10 Correct 135 ms 9808 KB Output is correct
11 Correct 131 ms 9984 KB Output is correct

Subtask #4
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6592 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6588 KB Output is correct
5 Correct 3 ms 6496 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 5 ms 6544 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 7 ms 6656 KB Output is correct
10 Correct 7 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6600 KB Output is correct
13 Correct 7 ms 6612 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct
15 Correct 7 ms 6664 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 5 ms 6612 KB Output is correct
18 Correct 91 ms 8956 KB Output is correct
19 Correct 118 ms 9688 KB Output is correct
20 Correct 70 ms 8396 KB Output is correct
21 Correct 123 ms 9680 KB Output is correct
22 Correct 128 ms 9660 KB Output is correct
23 Correct 143 ms 9724 KB Output is correct
24 Correct 135 ms 9808 KB Output is correct
25 Correct 135 ms 9936 KB Output is correct
26 Correct 137 ms 9808 KB Output is correct
27 Correct 135 ms 9808 KB Output is correct
28 Correct 131 ms 9984 KB Output is correct
29 Correct 136 ms 11656 KB Output is correct
30 Correct 134 ms 8388 KB Output is correct
31 Correct 261 ms 9864 KB Output is correct
32 Correct 726 ms 13604 KB Output is correct
33 Correct 297 ms 10176 KB Output is correct
34 Correct 304 ms 10332 KB Output is correct
35 Correct 183 ms 9048 KB Output is correct
36 Correct 110 ms 8144 KB Output is correct
37 Correct 133 ms 8492 KB Output is correct
38 Correct 152 ms 9784 KB Output is correct
39 Correct 149 ms 9800 KB Output is correct
40 Correct 146 ms 9800 KB Output is correct
41 Correct 152 ms 9928 KB Output is correct
42 Correct 148 ms 9680 KB Output is correct
43 Correct 180 ms 11464 KB Output is correct
44 Correct 187 ms 11320 KB Output is correct
45 Correct 188 ms 11336 KB Output is correct
46 Correct 178 ms 11340 KB Output is correct
47 Correct 180 ms 11324 KB Output is correct
48 Correct 954 ms 9796 KB Output is correct
49 Correct 960 ms 9872 KB Output is correct
50 Correct 468 ms 10184 KB Output is correct
51 Correct 468 ms 10068 KB Output is correct
52 Correct 1746 ms 9808 KB Output is correct
53 Correct 1589 ms 9680 KB Output is correct
54 Correct 963 ms 9680 KB Output is correct