제출 #1142508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142508		AtabayRajabli	Izbori (COCI22_izbori)	C++20	0 / 110	12 ms	5956 KiB

Main

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 5, inf = 1e9 + 7;
int n, a[sz], fr[sz], p[3][sz];

struct FW
{
    vector<int> f;
    int n;
    FW(int len)
    {
        n = 2 * len + 5;
        f.resize(2 * n + 5, 0);
    }
    void add(int i)
    {
        for(; i < n; i += i & -i) f[i]++;
    }
    int get(int i)
    {
        int r = 0;
        for(; i > 0; i -= i & -i) r += f[i];
        return r;
    }
};

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        p[1][i] = p[1][i - 1] + (a[i] == 1);
        p[2][i] = p[2][i - 1] + (a[i] == 2);
    }

    FW f1(n), f2(n);
    f1.add(0 + n + 5);
    f2.add(0 + n + 5);
    for(int i = 1; i <= n; i++)
    {
        int v1 = 2 * p[1][i] - i;
        int v2 = 2 * p[2][i] - i;
        ans += f1.get(v1 - 1 + n + 5);
        ans += f2.get(v2 - 1 + n + 5);
        f1.add(v1 + n + 5);
        f2.add(v2 + n + 5);
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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