Submission #696681

#	Time	Username	Problem	Language	Result	Execution time	Memory
696681		Tuanlinh123	Izbori (COCI22_izbori)	C++17	40 / 110	49 ms	17560 KiB

Main

// #define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

ll a[200005], cnt[200005];
vector <ll> num;
map <ll, ll> Map;

struct BIT
{
    ll n;
    vector <ll> bit;

    BIT(ll n): n(n)
    {
        bit.assign(n+1, 0);
    }

    void update(ll i, ll val)
    {
        for (i; i<=n; i+=i&(-i))
            bit[i]+=val;
    }

    ll query(ll l, ll r)
    {
        ll ans=0; l--;
        for (r; r>0; r-=r&(-r))
            ans+=bit[r];
        for (l; l>0; l-=l&(-l))
            ans-=bit[l];
        return ans;
    }
};

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    ll n; cin >> n;
    ll Max=0;
    for (ll i=1; i<=n; i++)
    {
        cin >> a[i]; Max=max(Max, a[i]);
        if (Map[a[i]]==0)
        {
            num.pb(a[i]);
            Map[a[i]]=1;
        }
    }
    for (ll i=0; i<num.size(); i++)
        Map[num[i]]=i+1;
    for (ll i=1; i<=n; i++)
        a[i]=Map[a[i]];
    if (Max<=2)
    {
        ll ans=0;
        BIT A0(n*5), A1(n*5);
        A0.update(n+1, 1);
        A1.update(n+1, 1);
        ll cnt0=0, cnt1=0;
        for (ll i=1; i<=n; i++)
        {
            cnt0+=a[i]==1;
            cnt1+=a[i]==2;
            ans+=A0.query(1, cnt0*2-i+n);
            ans+=A1.query(1, cnt1*2-i+n);
            // cout << cnt0*2-i+n << " " << cnt1*2-i+n << "\n";
            A0.update(cnt0*2-i+n+1, 1);
            A1.update(cnt1*2-i+n+1, 1);
        // cout << "bruh" << flush;
        }
        cout << ans;
        return 0;
    }
    if (n<=3000)
    {
        ll ans=0;
        for (ll i=1; i<=n; i++)
        {
            ll Max=0;
            for (ll j=1; j<=n; j++)
                cnt[a[j]]=0;
            for (ll j=i; j<=n; j++)
            {
                cnt[a[j]]++;
                Max=max(Max, cnt[a[j]]);
                if (Max>j-i+1-Max)
                    ans++;
            }
        }
        cout << ans;
        return 0;
    }
}

Compilation message (stderr)

Main.cpp: In member function 'void BIT::update(long long int, long long int)':
Main.cpp:31:14: warning: statement has no effect [-Wunused-value]
   31 |         for (i; i<=n; i+=i&(-i))
      |              ^
Main.cpp: In member function 'long long int BIT::query(long long int, long long int)':
Main.cpp:38:14: warning: statement has no effect [-Wunused-value]
   38 |         for (r; r>0; r-=r&(-r))
      |              ^
Main.cpp:40:14: warning: statement has no effect [-Wunused-value]
   40 |         for (l; l>0; l-=l&(-l))
      |              ^
Main.cpp: In function 'int main()':
Main.cpp:67:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (ll i=0; i<num.size(); i++)
      |                  ~^~~~~~~~~~~

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