Problem D2: Work-Life Balance - Chapter 2

c++

#include <bits/stdc++.h>

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

using namespace std;

struct PairHash {inline std::size_t operator()(const std::pair<int, int> &v) const { return v.first * 31 + v.second; }};

// speed
#define Code ios_base::sync_with_stdio(false);
#define By ios::sync_with_stdio(0);
#define Sumfi cout.tie(NULL);

// alias
using ll = long long;
using ld = long double;
using ull = unsigned long long;

// constants
const ld PI = 3.14159265358979323846;  /* pi */
const ll INF = 1e18;
const ld EPS = 1e-9;
const ll MAX_N = 1010101;
const ll mod = 998244353;

// typedef
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef array<ll,3> all3;
typedef array<ll,5> all5;
typedef vector<all3> vall3;
typedef vector<all5> vall5;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
typedef unordered_map<pll, ll, PairHash> umpll;

// macros
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,m,n) for(ll i=n;i>=m;i--)
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define INF(a) memset(a,0x3f3f3f3f3f3f3f3fLL,sizeof(a))
#define ASCEND(a) iota(all(a),0)
#define sz(x) ll((x).size())
#define pyes cout<<"YES\n";
#define pno cout<<"NO\n";
#define pneg1 cout<<"-1\n";
#define ppossible cout<<"Possible\n";
#define pimpossible cout<<"Impossible\n";
#define TC(x) cout<<"Case #"<<x<<": ";
#define X first
#define Y second

// utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template<typename T>
void printv(vector<T>v){ll n=v.size();rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
void fileIO() {freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);}
void hackerCupIO() {freopen("/Users/summerflower/Downloads/worklife_balance_chapter_2_input.txt", "r", stdin); freopen("/Users/summerflower/Downloads/solution.txt","w",stdout);}
void readf() {freopen("", "rt", stdin);}
template<typename T>
void readv(vector<T>& v){rep(i,0,sz(v)) cin>>v[i];}
template<typename T, typename U>
void readp(pair<T,U>& A) {cin>>A.first>>A.second;}
template<typename T, typename U>
void readvp(vector<pair<T,U>>& A) {rep(i,0,sz(A)) readp(A[i]); }
void readvall3(vall3& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2];}
void readvvll(vvll& A) {rep(i,0,sz(A)) readv(A[i]);}

struct Combination {
    vll fac, inv;
    ll n, MOD;

    ll modpow(ll n, ll x, ll MOD = mod) { if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }

    Combination(ll _n, ll MOD = mod): n(_n + 1), MOD(MOD) {
        inv = fac = vll(n,1);
        rep(i,1,n) fac[i] = fac[i-1] * i % MOD;
        inv[n - 1] = modpow(fac[n - 1], MOD - 2, MOD);
        rrep(i,1,n - 2) inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    ll fact(ll n) {return fac[n];}
    ll nCr(ll n, ll r) {
        if(n < r or n < 0 or r < 0) return 0;
        return fac[n] * inv[r] % MOD * inv[n-r] % MOD;
    }
};

// geometry data structures
template <typename T>
struct Point {
    T y,x;
    Point(T y, T x) : y(y), x(x) {}
    Point() {}
    void input() {cin>>y>>x;}
    friend ostream& operator<<(ostream& os, const Point<T>& p) { os<<p.y<<' '<<p.x<<'\n'; return os;}
    Point<T> operator+(Point<T>& p) {return Point<T>(y + p.y, x + p.x);}
    Point<T> operator-(Point<T>& p) {return Point<T>(y - p.y, x - p.x);}
    Point<T> operator*(ll n) {return Point<T>(y*n,x*n); }
    Point<T> operator/(ll n) {return Point<T>(y/n,x/n); }

    Point<T> rotate(Point<T> center, ld angle) {
        ld si = sin(angle * PI / 180.), co = cos(angle * PI / 180.);
        ld y = this->y - center.y;
        ld x = this->x - center.x;

        return Point<T>(y * co - x * si + center.y, y * si + x * co + center.x);
    }
};

template<typename T>
struct Circle {
    Point<T> center;
    T radius;
    Circle(T y, T x, T radius) : center(Point<T>(y,x)), radius(radius) {}
    Circle() {}

    void input() {
        center = Point<T>();
        center.input();
        cin>>radius;
    }

    bool circumference(Point<T> p) {
        return (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y) == radius * radius;
    }

    bool intersect(Circle<T> c) {
        T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
        return (radius - c.radius) * (radius - c.radius) <= d and d <= (radius + c.radius) * (radius + c.radius);
    }
};

ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }
all3 __exgcd(ll x, ll y) { if(!y) return {x,1,0}; auto [g,x1,y1] = __exgcd(y, x % y); return {g, y1, x1 - (x/y) * y1}; }
ll __lcm(ll x, ll y) { return x / __gcd(x,y) * y; }
ll modpow(ll n, ll x, ll MOD = mod) { n%=MOD; if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }

ll fenwick[2][MAX_N];
ll fenwick2[2][MAX_N];

void update(ll n, ll key, ll v) {
    while(n < MAX_N) {
        fenwick[key][n] += v;
        n += n & -n;
    }
}

ll query(ll n, ll key) {
    ll res = 0;
    while(n) {
        res += fenwick[key][n];
        n -= n & - n;
    }
    return res;
}

void update2(ll n, ll key, ll v) {
    while(n < MAX_N) {
        fenwick2[key][n] += v;
        n += n & -n;
    }
}

ll query2(ll n, ll key) {
    ll res = 0;
    while(n) {
        res += fenwick2[key][n];
        n -= n & -n;
    }
    return res;
}

ll sum(ll a, ll b) {return a + b * 2;}

ll findLeft(ll l, ll r, ll k, ll total, ll v) {
    ll res = -INF;
    while(l <= r) {
        ll m = l + (r - l) / 2;
        ll count = total - query(m,v);
        if(count == k) res = max(res, m);
        if(count < k) r = m - 1;
        else l = m + 1;
    }
    return res + 1;
}

ll findRight(ll l, ll r, ll k, ll total, ll v) {
    ll res = INF;
    while(l <= r) {
        ll m = l + (r - l) / 2;
        ll count = query(m,v) - total;
        if(count == k) res = min(res, m);
        if(count < k) l = m + 1;
        else r = m - 1;
    }
    return res;
}

ll querySum(ll l, ll r, ll key) {
    return query2(r,key) - query2(l-1,key);
}

ll rangeSum(ll start, ll k) {
    return k * (2 * start + (k - 1)) / 2;
}

ll queryLeft(ll l, ll r, ll key, ll k) {
    return rangeSum(r-k+1,k) - querySum(l,r,key);
}

ll queryRight(ll l, ll r, ll key, ll k) {
    return querySum(l,r,key) - rangeSum(l,k);
}

ll solve(vll A, vall3 Q) {
    ZERO(fenwick);
    ZERO(fenwick2);
    ll freq[2] = {};
    rep(i,0,sz(A)) {
        update(i + 1, A[i] - 1, 1);
        update2(i+1,A[i]-1,i+1);
        freq[A[i] - 1]++;
    }
    ll res = 0;
    rep(i,0,sz(Q)) {
        auto [x,y,z] = Q[i];
        if(A[x-1] != y) {
            update(x, A[x-1] - 1, -1);
            update2(x,A[x-1] - 1,-x);
            freq[A[x-1] - 1]--;
            A[x-1] = y;
            freq[A[x-1] - 1]++;
            update(x, A[x-1] - 1, 1);
            update2(x,A[x-1] - 1,x);
        }
        ll s = sum(freq[0], freq[1]);
        if(s & 1 or !(z <= s / 2 and s / 2 <= 2 * z)) res -= 1;
        else {
            ll target = s / 2;
            ll a = query(z,0), b = query(z,1);
            ll lsum = sum(a,b);
            if(lsum == target) continue;
            ll change = abs(target - lsum);
            if(lsum < target) {
                if(a < change or freq[1] - b < change) {
                    res += -1;
                }
                else {
                    ll left = findLeft(0,z,change,a,0), right = findRight(z+1,sz(A) + 2, change,b,1);
                    res += queryLeft(left,z,0,change) + queryRight(z+1,right,1,change) + change * change;
                }
            } else if(lsum > target) {
                if(b < change or freq[0] - a < change) {
                    res += -1;
                }
                else {
                    ll left = findLeft(0, z, change, b, 1), right = findRight(z + 1, sz(A) + 2, change, a, 0);
                    res += queryLeft(left,z,1,change) + queryRight(z+1,right,0,change) + change * change;
                }
            }
        }
    }
    return res;
}

int main() {
    Code By Sumfi
    cout.precision(12);
    ll tc = 1;
    hackerCupIO();
    cin>>tc;
    rep(i,1,tc+1) {
        ll n, m;
        cin>>n>>m;
        vll A(n);
        vall3 Q(m);
        readv(A);
        readvall3(Q);
        TC(i) print(solve(A,Q));
    }
    return 0;
}