Submission #972269

#	Time	Username	Problem	Language	Result	Execution time	Memory
972269		RandomUser	Izbori (COCI22_izbori)	C++17	110 / 110	1754 ms	23520 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
 
struct BIT {
    int n;
    vector<int> tree;
 
    BIT(int _n) {
        n = _n + 10;
        tree.resize(_n+60);
    }
 
    void update(int p, int v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }
 
    int query(int p) {
        int ans = 0;
        for(p++; p>0; p-=p&-p) ans += tree[p];
        return ans;
    }
 
    int query(int l, int r) { return query(r) - query(l-1); }
    void reset() { for(int &x : tree) x = 0; }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
 
    int n;
    ll ans = 0;
    cin >> n;
    int B = sqrt(n);
 
    vector<int> v(n+1), comp;
    map<int, int> cnt;
    map<int, vector<int> > mp;
    for(int i=1; i<=n; i++) {
        cin >> v[i];
        if(++cnt[v[i]] == 1) {
            comp.push_back(v[i]);
            mp[v[i]].push_back(0);
        }
        mp[v[i]].push_back(i);
    }
 
    BIT bit(2*n+1000);
    for(int &x : comp) {
        if(cnt[x] >= B) {
            int sum = 0;
            bit.update(n+1, 1);
            for(int i=1; i<=n; i++) {
                sum += (v[i] == x);
                ans += bit.query(2*sum - i - 1 + (n + 1));
                bit.update(2*sum - i + (n + 1), 1);
            }
            bit.reset();
        } else {
            ans += cnt[x];
 
            mp[x].push_back(n+1);
 
            for(int i=1; i<mp[x].size()-1; i++) {
                for(int j=i+1; j<mp[x].size()-1; j++) {
                    if(2 * (j - i + 1) <= mp[x][j] - mp[x][i] + 1) continue;
                    int left = 2 * (j - i + 1) - (mp[x][j] - mp[x][i] + 1) - 1;
                    int L = min(left, mp[x][i] - mp[x][i-1] - 1);
                    int R = mp[x][j+1] - mp[x][j] - 1;
                    ans += L + 1;
 
                    if(left < R) {
                        ans += 1ll * left * (left + 1) / 2;
                    } else {
                        ans += R * (left - R + 1);
                        ans += 1ll * (R - 1) * R / 2;
                    }
                }
            }
        }
    }
 
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i=1; i<mp[x].size()-1; i++) {
      |                          ~^~~~~~~~~~~~~~~
Main.cpp:69:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for(int j=i+1; j<mp[x].size()-1; j++) {
      |                                ~^~~~~~~~~~~~~~~

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