제출 #1165431

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

Main

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

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

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

void check(int x) {
        for (int i = 0; i < n; i++)
                ps[i + 1] = ps[i] + (a[i] == x) - (a[i] != x);
        int tmp = 0;
        cnt2[ps[n]]++;
        for (int 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 (int i = 0; i < n; i++)
                cin >> a[i];
}

void solve() {
        compress();
        for (int i = 0; i < n; i++) {
                cnt[a[i]]++;
                if (cnt[a[i]] == SQ)
                        check(a[i]);
        }
        for (int i = 0; i < n; i++) {
                int maxi = 0, p = 0;
                for (int 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 (int 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: 0 / 15
• Subtask 4: 0 / 70