제출 #1055736

#제출 시각아이디문제언어결과실행 시간메모리
1055736manhlinh1501Izbori (COCI22_izbori)C++17
110 / 110
2379 ms22444 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int MAXN = 5e5 + 5; const int BLOCK_SIZE = 475; #define ALL(a) (a).begin(), (a).end() #define LB(a, x) (lower_bound(ALL(a), x) - (a).begin() + 1) int N; int a[MAXN]; vector<int> pos[MAXN]; int prefix[MAXN]; int cnt[MAXN]; struct fenwick { int N; int tree[MAXN]; void update(int x, int v) { for(; x < MAXN; x += (x & -x)) tree[x] += v; } int calc(int x) { int res = 0; for(; x; x -= (x & -x)) res += tree[x]; return res; } } BIT; void compress() { vector<int> temp; for(int i = 1; i <= N; i++) temp.emplace_back(a[i]); sort(ALL(temp)); temp.resize(unique(ALL(temp)) - temp.begin()); for(int i = 1; i <= N; i++) a[i] = LB(temp, a[i]); } signed main() { #define TASK "baucu" if (fopen(TASK ".inp", "r")) { freopen(TASK ".inp", "r", stdin); freopen(TASK ".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for(int i = 1; i <= N; i++) cin >> a[i]; compress(); for(int i = 1; i <= N; i++) pos[a[i]].emplace_back(i); i64 ans = 0; for(int i = 1; i <= N; i++) { int maxx = 0; for(int j = i; j <= min(N, i + 2 * BLOCK_SIZE - 1); j++) { if(pos[a[j]].size() <= BLOCK_SIZE) { cnt[a[j]]++; maxx = max(maxx, cnt[a[j]]); } if(maxx * 2 > (j - i + 1)) ans++; } for(int j = i; j <= min(N, i + 2 * BLOCK_SIZE - 1); j++) { if(pos[a[j]].size() <= BLOCK_SIZE) cnt[a[j]]--; } } BIT.update(N + 1, 1); for(int i = 1; i <= N; i++) { if(pos[i].size() > BLOCK_SIZE) { for(int j = 1; j <= N; j++) prefix[j] = -1; for(int p : pos[i]) prefix[p] = 1; for(int j = 1; j <= N; j++) prefix[j] += prefix[j - 1]; for(int j = 1; j <= N; j++) prefix[j] += (N + 1); for(int j = 1; j <= N; j++) { ans += BIT.calc(prefix[j] - 1); BIT.update(prefix[j], 1); } for(int j = 1; j <= N; j++) BIT.update(prefix[j], -1); } } cout << ans; return (0 ^ 0); }

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

Main.cpp: In function 'int main()':
Main.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         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...