Submission #635052

#	Time	Username	Problem	Language	Result	Execution time	Memory
635052		Tuanlinh123	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1 ms	340 KiB

joi2019_ho_t3

#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/freopen/"

ll a[300005], pre[300005], suf[300005];

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;
        for (r; r>0; r-=r&(-r))
            ans+=bit[r];
        l--;
        for (l; l>0; l-=l&(-l))
            ans-=bit[l];
        return ans;
    }
};

map <ll, ll> Map;
vector <ll> num;

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;
    for (ll i=1; i<=n; i++)
    {
        cin >> a[i];
        if (Map[a[i]]==0)
        {
            Map[a[i]]=1;
            num.pb(a[i]); 
        }
    }
    ll k=num.size();
    sort(num.begin(), num.end());
    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]];
    BIT A(k), B(k);
    for (ll i=1; i<=n; i++)
    {
        pre[i]=pre[i-1]+A.query(a[i]+1, k);
        // cout << A.query(a[i]+1, k) << "\n";
        A.update(a[i], 1);
    }
    for (ll i=n; i>=1; i--)
    {
        suf[i]=suf[i+1]+B.query(a[i]+1, k);
        B.update(a[i], 1);
    }
    // for (ll i=1; i<=n; i++)
    //     cout << a[i] << " " << pre[i] << " " << suf[i] << "\n";
    ll ans=LLONG_MAX;
    for (ll i=1; i<=n; i++)
        ans=min(ans, min(pre[i-1]+suf[i], pre[i]+suf[i+1]));
    cout << ans << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In member function 'void BIT::update(long long int, long long int)':
joi2019_ho_t3.cpp:28:14: warning: statement has no effect [-Wunused-value]
   28 |         for (i; i<=n; i+=i&(-i))
      |              ^
joi2019_ho_t3.cpp: In member function 'long long int BIT::query(long long int, long long int)':
joi2019_ho_t3.cpp:35:14: warning: statement has no effect [-Wunused-value]
   35 |         for (r; r>0; r-=r&(-r))
      |              ^
joi2019_ho_t3.cpp:38:14: warning: statement has no effect [-Wunused-value]
   38 |         for (l; l>0; l-=l&(-l))
      |              ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:69: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]
   69 |     for (ll i=0; i<num.size(); i++)
      |                  ~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25