Submission #696720

#	Time	Username	Problem	Language	Result	Execution time	Memory
696720		tranxuanbach	Izbori (COCI22_izbori)	C++17	110 / 110	198 ms	14656 KiB

Main

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

template<class T>
struct range_add_range_sum_query_solver{
    int n;
    vector<T> data0, data1;
    range_add_range_sum_query_solver(){ }
    // O(n)
    range_add_range_sum_query_solver(int n): n(n), data0(n), data1(n){ }
    // O(n)
    range_add_range_sum_query_solver(int n, T init): range_add_range_sum_query_solver(vector<T>(n, init)){ }
    // O(n)
    range_add_range_sum_query_solver(const vector<T> &v): n((int)v.size()), data0(n), data1(v){
        for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data1[i + (i & -i) - 1] += data1[i - 1];
    }
    void update(int ql, int qr, T x){
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        for(auto l = ql + 1; l <= n; l += l & -l) data0[l - 1] += x, data1[l - 1] -= ql * x;
        for(auto r = qr + 1; r <= n; r += r & -r) data0[r - 1] -= x, data1[r - 1] += qr * x;
    }
    T pref(int qr) const{
        assert(0 <= qr && qr <= n);
        T sum0 = {}, sum1 = {};
        for(auto r = qr; r > 0; r -= r & -r) sum0 += data0[r - 1], sum1 += data1[r - 1];
        return qr * sum0 + sum1;
    }
    T query(int l, int r) const{
        assert(0 <= l && l <= r && r <= n);
        return pref(r) - pref(l);
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, const range_add_range_sum_query_solver<T> &solver){
        out << "[";
        for(auto i = 0; i < solver.n; ++ i){
            out << solver.query(i, i + 1);
            if(i != solver.n - 1) out << ", ";
        }
        return out << ']';
    }
};

const int N = 2e5 + 5;

range_add_range_sum_query_solver <int> seg(2 * N);

int n;
int a[N];
vi b[N];

void compress(){
    vi b(a + 1, a + n + 1);
    sort(bend(b));
    b.erase(unique(bend(b)), b.end());
    ForE(i, 1, n){
        a[i] = lower_bound(bend(b), a[i]) - b.begin() + 1;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n;
    ForE(i, 1, n){
        cin >> a[i];
    }

    compress();
    ForE(i, 1, n){
        b[a[i]].emplace_back(i);
    }

    ll ans = 0;
    ForE(val, 1, n){
        vpii updates;
        updates.emplace_back(0 + N, 1 + N);
        seg.update(0 + N, 1 + N, 1);

        int sum = 0;
        int l = 1;
        Fora(i, b[val]){
            int r = i - 1;
            if (l <= r){
                int vall = 2 * sum - r, valr = 2 * sum - l;
                for (int j = valr; j >= vall; j--){
                    int tans = seg.pref(j + N);
                    if (tans == 0){
                        break;
                    }
                    ans += tans;
                }
                updates.emplace_back(vall + N, valr + 1 + N);
                seg.update(vall + N, valr + 1 + N, 1);
            }

            l = r + 1;
            sum++;
        }
        int r = n;
        int vall = 2 * sum - r, valr = 2 * sum - l;
        for (int j = valr; j >= vall; j--){
            int tans = seg.pref(j + N);
            if (tans == 0){
                break;
            }
            ans += tans;
        }
        Fora(update, updates){
            seg.update(update.fi, update.se, -1);
        }
    }
    cout << ans << endl;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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