Submission #1055736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055736		manhlinh1501	Izbori (COCI22_izbori)	C++17	110 / 110	2379 ms	22444 KiB

Main

#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);
}

Compilation message (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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70