Submission #972262

#	Time	Username	Problem	Language	Result	Execution time	Memory
972262		RandomUser	Izbori (COCI22_izbori)	C++17	40 / 110	3006 ms	4592 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;
    for(int i=1; i<=n; i++) {
        cin >> v[i];
        if(++cnt[v[i]] == 1) comp.push_back(v[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];
 
            vector<int> p; p.push_back(0);
            for(int i=1; i<=n; i++)
                if(v[i] == x) p.push_back(i);
            p.push_back(n+1);
 
            for(int i=1; i<p.size()-1; i++) {
                for(int j=i+1; j<p.size()-1; j++) {
                    if(2 * (j - i + 1) <= p[j] - p[i] + 1) continue;
                    int left = 2 * (j - i + 1) - (p[j] - p[i] + 1) - 1;
                    int L = min(left, p[i] - p[i-1] - 1);
                    int R = p[j+1] - p[j] - 1;
                    //for(int k=0; k<=L; k++) ans += min(R, left - k);
                    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:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=1; i<p.size()-1; i++) {
      |                          ~^~~~~~~~~~~
Main.cpp:67:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 for(int j=i+1; j<p.size()-1; j++) {
      |                                ~^~~~~~~~~~~

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