제출 #1142928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142928		HasanV11010238	Izbori (COCI22_izbori)	C++20	25 / 110	3035 ms	5932 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 300000
#define mod 1000000007
int ti;
vector<ll> f;
void update(int x){
    for (; x <= ti; x = (x | (x + 1))){
        f[x]++;
    }
}
ll query(int r){
    ll ans = 0;
    for (; r > 0; r = (r & (r + 1)) - 1){
        ans += f[r];
    }
    return ans;
}
int n;
ll ans = 0;
vector<int> v;
void calc(int x){
    f.assign(2 * n + 3, 0);
    update(n);
    int pr = 0;
    for (int i = 1; i <= n; i++){
        if (v[i] == x) pr++;
        else pr--;
        ans += query(pr - 1 + n);
        update(pr + n);
    }
}
const int bl = 2000;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    v.assign(n + 1, 0);
    set<int> se;
    map<int, int> ma;
    for (int i = 1; i <= n; i++){
        cin>>v[i];
        se.insert(v[i]);
    }
    ti = 2 * n + 2;
    int no = 1;
    for (auto el : se){
        ma[el] = no;
        no++;
    }
    vector<int> cn(n + 1, 0), cnt(n + 1, 0);
    for (int i = 1; i <= n; i++){
        v[i] = ma[v[i]];
    }
    for (int i = 1; i <= n; i++){
        cn[v[i]]++;
        if (cn[v[i]] == bl + 1){
            calc(v[i]);
        }
    }
    for (int i = 1; i <= n; i++){
        int to = min(i + 2 * bl, n), wh = 0;
        int ma = 0;
        for (int j = i; j <= to; j++){
            cnt[v[j]]++;
            if (cnt[v[j]] > ma){
                ma++;
                wh = v[j];
            }
            if (ma * 2 > (j - i + 1) && cn[wh] <= bl){
                ans++;
            }
        }
        for (int j = i; j <= to; j++){
            cnt[v[j]]--;
        }
    }
    cout<<ans<<"\n";
}

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