제출 #1165437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165437		A_M_Namdar	Izbori (COCI22_izbori)	C++20	110 / 110	487 ms	12536 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const long long N = 2e5 + 10, SQ = 300;
long long n, a[N], ps[N], cnt[N * 2], cnt2[N * 2], ans;

void compress() {
        set<long long> s;
        map<long long, long long> id;
        for (long long i = 0; i < n; i++)
                s.insert(a[i]);
        for (long long i = 0; !s.empty(); i++) {
                id[*s.begin()] = i;
                s.erase(s.begin());
        }
        for (long long i = 0; i < n; i++)
                a[i] = id[a[i]];
}

void check(long long x) {
        ps[0] = N;
        for (long long i = 0; i < n; i++)
                ps[i + 1] = ps[i] + (a[i] == x) - (a[i] != x);
        long long tmp = 0;
        cnt2[ps[n]]++;
        for (long long i = n - 1; i >= 0; i--) {
                if (ps[i + 1] > ps[i]) tmp += cnt2[ps[i + 1]];
                else                   tmp -= cnt2[ps[i]];
                ans += tmp;
                cnt2[ps[i]]++;
        }
        memset(cnt2, 0, sizeof cnt2);
}

void input() {
        cin >> n;
        for (long long i = 0; i < n; i++)
                cin >> a[i];
}

void solve() {
        compress();
        for (long long i = 0; i < n; i++) {
                cnt[a[i]]++;
                if (cnt[a[i]] == SQ)
                        check(a[i]);
        }
        for (long long i = 0; i < n; i++) {
                long long maxi = 0, p = 0;
                for (long long j = i; j < min(n, i + SQ * 2); j++) {
                        cnt2[a[j]]++;
                        if (maxi < cnt2[a[j]]) maxi = cnt2[a[j]], p = a[j];
                        if (maxi * 2 > j - i + 1 && cnt[p] < SQ)
                                ans++;
                }
                for (long long j = i; j < min(n, i + SQ * 2); j++)
                        cnt2[a[j]]--;
        }
        cout << ans;
}

int main() {
        ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
        input();
        solve();
}

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