Submission #1003416

#TimeUsernameProblemLanguageResultExecution timeMemory
1003416WhisperIzbori (COCI22_izbori)C++17
40 / 110
3069 ms15668 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; //#define int long long #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, a, b) for (int i = (b); i >= (a); i --) #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPD(i, n) for (int i = (n) - 1; i >= 0; --i) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Phu Trong from Nguyen Tat Thanh High School for gifted student */ template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } #define MAX 200005 #define BLOCK_SIZE 400 #define off_set 200000 int nArr; int A[MAX]; vector<int> pos[MAX]; template<class T = vector<int>> T unique (T v){ sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); return v; } template<class T = int> T find(T x, const vector<int>& v){ return (int)(lower_bound(v.begin(), v.end(), x) - v.begin() + 1); } bool hvy[MAX]; int cnt[MAX]; struct custom_hash{ size_t operator ()(uint64_t x) const{ static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); x ^= FIXED_RANDOM; return x ^ (x >> 16); } }; template<class T = int> struct FenwickTree{ T *F = nullptr; vector<pair<int, int>> opt; int n; FenwickTree(int _n = 0){ resize(_n); } void reset(void){ fill (F, F + n + 1, T(0)); } void resize(int _n){ if(F != nullptr) delete[] F; this -> n = _n; F = new T [n + 5]; reset(); } void Modify(int p, int val, int c){ if (c) opt.emplace_back(p, -val); for (; p <= n; p += p & (-p)) F[p] += val; } T Query(int p){ int res = 0; for (; p > 0; p -= p & (-p)) res += F[p]; return res; } void rollback(){ while ((int)opt.size()){ int p, val; tie(p, val) = opt.back(); Modify(p, val, 0); opt.pop_back(); } } int upper_bound(T val){ int res = 0; for (int i = __lg(n); i >= 0; --i) { if ((res | MASK(i)) <= n && val >= F[res | MASK(i)]){ val -= F[res | MASK(i)]; res |= MASK(i); } } return res + 1; } int lower_bound(T val){ int res = 0; for (int i = __lg(n); i >= 0; --i){ if ((res | MASK(i)) <= n && val > F[res | MASK(i)]){ val -= F[res | MASK(i)]; res |= MASK(i); } } return res + 1; } }; void process(void){ cin >> nArr; vector<int> comp; for (int i = 1; i <= nArr; ++i) cin >> A[i], comp.push_back(A[i]); comp = unique(comp); for (int i = 1; i <= nArr; ++i) A[i] = find(A[i], comp), cnt[A[i]]++; for (int i = 1; i <= nArr; ++i) { hvy[i] = (cnt[i] >= BLOCK_SIZE); } long long ans = 0; for (int l = 1; l <= nArr; ++l){ int max_occurence = 0; unordered_map<int, int, custom_hash> g; for (int r = l; r <= nArr && (r - l + 1 < 2 * BLOCK_SIZE); ++r){ if(hvy[A[r]]) continue; g[A[r]]++; maximize(max_occurence, g[A[r]]); if (2 * max_occurence > (r - l + 1)) ++ans; } } FenwickTree<long long> fen(2 * MAX); for (int i = 1; i <= nArr; ++i){ if (!hvy[i]) continue; vector<int> sm(nArr + 5); for (int j = 1; j <= nArr; ++j) sm[j] = sm[j - 1] + (A[j] == i ? 1 : -1); fen.Modify(off_set, 1, 1); for (int j = 1; j <= nArr; ++j){ ans += fen.Query(sm[j] + off_set - 1); fen.Modify(sm[j] + off_set, 1, 1); } fen.rollback(); } cout << ans; } signed main(){ #define name "Whisper" cin.tie(nullptr) -> sync_with_stdio(false); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); process(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...