Submission #730494

#	Time	Username	Problem	Language	Result	Execution time	Memory
730494		huutuan	Izbori (COCI22_izbori)	C++14	110 / 110	2588 ms	4300 KiB

Main

#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int S=450, N=2e5+1, M=N*2+10;
int n, a[N], s[N], t[M];
int cnt[N], mp[N];

void update(int pos, int val){
    for (int i=pos; i<M; i+=i&(-i)) t[i]+=val;
}

int get(int pos){
    if (pos<0) return 0;
    int sum=0;
    for (int i=pos; i; i-=i&(-i)) sum+=t[i];
    return sum;
}

void solve(){
    cin >> n;
    long long ans=0;
    for (int i=1; i<=n; ++i) cin >> a[i];
    vector<int> sus(a+1, a+n+1);
    sort(all(sus)); sus.resize(unique(all(sus))-sus.begin());
    for (int i=1; i<=n; ++i) a[i]=lower_bound(all(sus), a[i])-sus.begin()+1;
    for (int i=1; i<=n; ++i) ++mp[a[i]];
    for (int l=1; l<=n; ++l){
        int mx=0;
        for (int r=l; r<=n && r-l+1<=2*S; ++r){
            if (mp[a[r]]<=S){
                ++cnt[a[r]];
                mx=max(mx, cnt[a[r]]);
            }
            if (mx*2>r-l+1) ++ans;
        }
        for (int r=l; r<=n && r-l+1<=2*S; ++r){
            if (mp[a[r]]<=S) --cnt[a[r]];
        }
    }
    for (int i=1; i<=n; ++i){
        if (mp[i]<=S) continue;
        memset(s, 0, sizeof s);
        memset(t, 0, sizeof t);
        for (int j=1; j<=n; ++j) if (a[j]==i) ++s[j]; else --s[j];
        partial_sum(s, s+n+1, s);
        update(0+n+1, 1);
        for (int j=1; j<=n; ++j){
            ans+=get(s[j]-1+n+1);
            update(s[j]+n+1, 1);
        }
    }
    cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int ntests=1;
    // cin >> ntests;
    while (ntests--) solve();
    return 0;
}

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