제출 #764858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764858		drdilyor	Izbori (COCI22_izbori)	C++17	40 / 110	3058 ms	5324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;

struct Fenwick {
    int n;
    vector<int> tree;
    Fenwick() = default;
    Fenwick(int n) : n(n), tree(n) {}
    int sum(int r) {
        int s = 0;
        for (; r >= 0; r = (r&(r+1))-1) s+= tree[r];
        return s;
    }
    void inc(int i, int d=1) {
        for (; i < n; i |= i+1) tree[i] += d;
    }
};


int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int& i : arr) cin >> i;
    set<int> poss(arr.begin(), arr.end());

    ll cnt = 0;
    for (int x : poss) {
        vector<int> brr(n+1);
        brr[0] = n;
        for (int i = 0; i < n; i++){ 
            brr[i+1] = brr[i] + (arr[i] == x ? 1 : -1);
        }
        Fenwick t(n*2+1);
        t.inc(brr[0]);
        for (int i = 1; i <= n; i++) {
            cnt += t.sum(brr[i]-1);
            t.inc(brr[i]);
        }
    }
    cout << cnt << '\n';
}

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