Submission #1261977

#TimeUsernameProblemLanguageResultExecution timeMemory
1261977shidou26Izbori (COCI22_izbori)C++20
110 / 110
604 ms19196 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define fi first #define se second #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() #define filter(v) v.resize(unique(all(v)) - v.begin()) #define dbg(x) "[" #x << " = " << x << "]" mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> bool maximize(T &a, T b) { if(a < b) return a = b, true; else return false; } template<typename T> bool minimize(T &a, T b) { if(a > b) return a = b, true; else return false; } template<typename T1, typename T2> T2 rnd(T1 l, T2 r) { return uniform_int_distribution<T2>(l, r)(rng); } typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<long long, int> pli; typedef pair<long long, long long> pll; const int N = 4e5 + 3; const int S = 500; int n; int a[N]; int cnt[N]; ll answer = 0; vector<int> cps; vector<int> color[N]; void process() { sort(all(cps)); filter(cps); for(int i = 1; i <= n; i++) { a[i] = lower_bound(all(cps), a[i]) - cps.begin() + 1; color[a[i]].push_back(i); } for(int c = 1; c <= n; c++) { if(sz(color[c]) >= S) { int prefix = n, total = 0; fill(cnt, cnt + 1 + 2 * n, 0); cnt[prefix]++; for(int i = 1; i <= n; i++) { int value = (a[i] == c ? 1 : -1); prefix += value; if(value == 1) total += cnt[prefix - 1]; else total -= cnt[prefix]; cnt[prefix]++; answer += total; } } } fill(cnt, cnt + 1 + n, 0); for(int i = 1; i <= n; i++) { int bound = min(n, i + 2 * S - 1), dominate = 0; for(int j = i; j <= bound; j++) { if(sz(color[a[j]]) < S) { cnt[a[j]]++; maximize(dominate, cnt[a[j]]); if(dominate >= (j - i + 1) / 2 + 1) answer++; } } for(int j = i; j <= bound; j++) cnt[a[j]] = 0; } cout << answer << endl; } void input() { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; cps.push_back(a[i]); } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); #define task "VBAUCU" if(fopen(task".INP", "r")) { freopen(task".INP", "r", stdin); freopen(task".OUT", "w", stdout); } int testcase = 1; // cin >> testcase; for(int i = 1; i <= testcase; i++) { input(); process(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...