제출 #755455

#제출 시각아이디문제언어결과실행 시간메모리
755455MilosMilutinovicIzbori (COCI22_izbori)C++14
40 / 110
3055 ms2252 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; const int M = 2 * N; const int B = sqrt(N * 1.87); int n, a[N], c[M], cnt[N], occ[N]; void modify(int p, int v) { for (p += N; p < M; p += p & -p) c[p] += v; } int query(int p) { int res = 0; for (p += N; p > 0; p -= p & -p) res += c[p]; return res; } void compress() { vector<int> xs; for (int i = 1; i <= n; i++) xs.push_back(a[i]); sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 1; i <= n; i++) { a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin()) + 1; } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } compress(); for (int i = 1; i <= n; i++) { occ[a[i]] += 1; } long long ans = 0; for (int v = 1; v <= n; v++) { if (occ[v] >= B) { modify(0, +1); int bal = 0; for (int i = 1; i <= n; i++) { bal += (a[i] == v ? 1 : -1); ans += query(bal - 1); modify(bal, +1); } modify(0, -1); bal = 0; for (int i = 1; i <= n; i++) { bal += (a[i] == v ? 1 : -1); modify(bal, -1); } } } for (int l = 1; l <= n; l++) { int f = a[l]; for (int r = l; r <= min(l + 2 * B, n); r++) { cnt[a[r]] += 1; if (cnt[a[r]] > cnt[f]) f = a[r]; if (cnt[f] * 2 > r - l + 1 && occ[f] < B) ans++; } for (int r = l; r <= min(l + 2 * B, n); r++) { cnt[a[r]] = 0; } } printf("%lld", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...