Submission #928858

#TimeUsernameProblemLanguageResultExecution timeMemory
928858a_l_i_r_e_z_aIzbori (COCI22_izbori)C++17
110 / 110
1996 ms23980 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() #define len(x) ((int)(x).size()) const int maxn = 2e5 + 5; const int inf = 1e9 + 7; int n, a[maxn]; set<int> st; map<int, int> dp; ll dac(int l, int r){ if(l >= r) return 0; if(l == r - 1) return 1; int mid = (l + r) / 2; st.clear(); dp.clear(); for(int i = mid - 1; i >= l; i--){ dp[a[i]]++; if(dp[a[i]] * 2 > mid - i) st.insert(a[i]); } dp.clear(); for(int i = mid; i < r; i++){ dp[a[i]]++; if(dp[a[i]] * 2 > i - mid + 1) st.insert(a[i]); } ll ans = 0; for(auto v: st){ dp.clear(); int prs = 0; dp[prs]++; for(int i = l; i < mid - 1; i++){ prs += (a[i] == v ? 1 : -1); dp[prs]++; } int sz = r - l; for(int i = -sz; i <= sz; i++) dp[i] += dp[i - 1]; prs += (a[mid - 1] == v ? 1 : -1); for(int i = mid; i < r; i++){ prs += (a[i] == v ? 1 : -1); ans += dp[prs - 1]; } } return ans + dac(l, mid) + dac(mid, r); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; cout << dac(0, n) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...