Cover them ALL using BIT

#1

mycode
i am sure i am missing out some very small detail…can u please give me a testcase where my code is failing??
my code works for the custom inputs/given cases…
i am getting a WA otherwise
(bahut der lagi h please help)
thankyou

#2

@shameek.agarwal could you please provide me your code.

#3 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(cont) cont.begin(), cont.end()
#define size 200010ll
#define mod 1000000007ll


bool mycomp(const pair<pair<ll, ll>, ll>&a, const pair<pair<ll, ll>, ll>&b)
{
    return a.fi.se < b.fi.se;
}


struct BIT
{
    ll tree[size];
    void clear()
    {
        for (ll i = 0; i < size; i++)
            tree[i] = 0;
    }
    ll query(ll idx)
    {
        ll retval = 0;
        while (idx > 0)
        {
            retval = (retval + tree[idx]) % mod;
            idx -= (idx & (-idx));
        }
        return retval;
    }
    void update(ll idx, ll val)
    {
        while (idx < size)
        {
            tree[idx] = (val + tree[idx]) % mod;
            idx += (idx & (-idx));
        }
    }
} BIT1, BIT2;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    ll t, n;
    cin >> t;
    while (t--)
    {

        cin >> n;
        vector<pair<pair<ll, ll>, ll>> arr;
        arr.reserve(n);
        vector<ll>compress(n);

        for (ll i = 0; i < n; i++)
        {
            cin >> compress[i];
            (arr[i].fi).fi = compress[i];
        }

        for (ll i = 0; i < n; i++)
            cin >> (arr[i].fi).se;

        sort(all(compress))5^ n,h;
        ll m = unique(all(compress)) - compress.begin();
        compress.resize(m);

        for (ll i = 0; i < n; i++)
            arr[i].se = (lower_bound(all(compress), (arr[i].fi).fi) - compress.begin()) + 1;

        sort(all(arr), mycomp);

        BIT1.clear();
        BIT2.clear();
        BIT1.update(arr[0].se, arr[0].fi.fi);
        BIT2.update(arr[0].se, 1);

        ll ans = 0;

        for (ll i = 1; i < n; i++)
        {


            ll greatersum = BIT1.query(size - 1) - BIT1.query(arr[i].se);
            ll greatercount = BIT2.query(size - 1) - BIT2.query(arr[i].se);

            ll lessersum = BIT1.query(arr[i].se - 1);
            ll lessercount = BIT2.query(arr[i].se - 1);


            ll val = arr[i].fi.fi;
            ll aaa = ( greatersum - ( (val * greatercount) % mod) ) % mod;
            ll bbb = ( ( (val * lessercount) % mod) - lessersum ) % mod;

            aaa = (aaa+mod)%mod;
            bbb = (bbb+mod)%mod;

            ll multi = arr[i].fi.se;

            // cout<<aaa<<" "<<bbb<<" "<<multi<<endl;

            ll curr = ( (aaa * multi) % mod + (bbb * multi) % mod ) % mod;
            ans = (ans + curr) % mod;

            BIT1.update(arr[i].se, arr[i].fi.fi);
            BIT2.update(arr[i].se, 1);


        }


        cout << ans << endl;

    }


    return 0;


}
#4

or please click on mycode…
thanks

#5

@shameek.agarwal I have made correction to your code, have a look at it.


Things that I found problematic are, use of reserve (look its definition)(it only reserve a memory but it does not effect size)
When to use int when to use long long (especially in case of bit operations as both have different bit size)
When performing subtraction under modulo take special care that number does not becomes negative.
If this resolves your doubt mark it resolved.

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.