제출 #768990

#제출 시각아이디문제언어결과실행 시간메모리
768990vjudge1Izbori (COCI22_izbori)C++17
10 / 110
91 ms9040 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...