AA TOI 23 #2 pC

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33mAt [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

void solve() {
    int N, C, Q; cin >> N >> C >> Q;

    int sum = 0;
    vector<int> A(N+1);
    for (int i = 1; i <= N; ++i) cin >> A[i], sum += A[i];

    int sum_large = sum, delta = 0;
    prior<int> large;
    Prior<int> small;
    multiset<int> nums, to_delete;

    auto balance = [&]() -> void {
        static auto it = end(to_delete);
        while (SZ(large) > sum / C + delta) {
            if ((it = to_delete.find(large.top())) != end(to_delete)) to_delete.erase(it), large.pop(), --delta;
            else small.ee(large.top()), sum_large -= large.top(), large.pop();
        }
        while (SZ(large) < sum / C + delta) {
            if ((it = to_delete.find(small.top())) != end(to_delete)) to_delete.erase(it), small.pop();
            else large.ee(small.top()), sum_large += large.top(), small.pop();
        }
        while (SZ(large) and (it = to_delete.find(large.top())) != end(to_delete)) to_delete.erase(it), large.pop(), --delta;
        while (SZ(small) and (it = to_delete.find(small.top())) != end(to_delete)) to_delete.erase(it), small.pop();
    };

    auto get_ans = [&]() -> int {
        int diff = sum % C;
        if (SZ(small)) {
            if (sum % C >= small.top()) return sum - sum_large - small.top();
            auto it_hi = nums.lower_bound(sum % C);
            auto it_lo = (it_hi != begin(nums) ? prev(it_hi) : end(nums));
            if (it_hi != end(nums) and *it_hi <= small.top()) chmin(diff, *it_hi - (sum % C)); //, debug(*it_hi - (sum % C));
            if (it_lo != end(nums) and *it_lo <= small.top()) chmin(diff, (sum % C) - *it_lo); //, debug((sum % C) - *it_lo);
        }
        // debug(sum, sum_large, diff);
        return sum - sum_large - (sum % C) + diff;
    };

    for (int i = 1; i <= N; ++i) large.ee(A[i]), nums.ee(A[i]);
    balance();

    cout << get_ans() << "\n";

    for (int q = 1, xi, vi; q <= Q; ++q) {
        cin >> xi >> vi;

        sum -= A[xi];
        if (SZ(large) and A[xi] >= large.top()) sum_large -= A[xi], ++delta;
        to_delete.ee(A[xi]);
        nums.erase(nums.find(A[xi]));

        A[xi] = vi;
        sum += A[xi];
        if (SZ(large) and A[xi] >= large.top()) sum_large += A[xi], large.ee(A[xi]);
        else small.ee(A[xi]);
        nums.ee(A[xi]);

        balance();
        cout << get_ans() << "\n";
    }
}

int32_t main() {
    fastIO();

    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}