Submission #768990

#	Time	Username	Problem	Language	Result	Execution time	Memory
768990		vjudge1	Izbori (COCI22_izbori)	C++17	10 / 110	91 ms	9040 KiB

Main

#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): 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);
	}
	int res = 0;
	Fenwick bit;
	auto heavy = [&](int i) {
		bit.reset();
		bit.add(up);
		int j = 0, cur = up;
		FOR(i, 1, n) {
			if (j < sz(s[i]) && i == 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) + 1);
		FOR(i, 1, n) {
			int len = min(n - i + 1, 2 * S - 1), 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 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70