Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

const int N = 500005;
const int INF = 1e9 + 9;

using namespace std;

struct node {
    int l, r;
    int delay;
    int minV, minPos;
    int minCnt;
    node *left, *right;

    node (int _l, int _r) {
        l = _l; r = _r;
        delay = 0;
        left = right = NULL;
    }

    void gatherMin() {
        minV = right->minV; minPos = right->minPos;
        if (left->minV < minV)
            minV = left->minV, minPos = left->minPos;
    }

    void gatherCnt() {
        minCnt = min(left->minCnt, right->minCnt);
    }

    void pushDown() {
        if (delay) {
            minCnt -= delay;
            if (l < r) {
                left->delay += delay;
                right->delay += delay;
            }
            delay = 0;
        }
    }

    void queryMin(int from, int &value, int &pos) {
        if (r < from) return;
        if (from <= l) {
            if (minV < value)
                value = minV, pos = minPos;
            return;
        }
        right->queryMin(from, value, pos);
        left->queryMin(from, value, pos);
    }

    void decSuffix(int from) {
        pushDown();
        if (r < from) return;
        if (from <= l) {
            delay += 2;
            pushDown();
            return;
        }
        left->decSuffix(from);
        right->decSuffix(from);
        gatherCnt();
    }

    void erase(int i) {
        if (r < i || i < l) return;
        if (l == r) {
            minV = INF;
            return;
        }
        left->erase(i);
        right->erase(i);
        gatherMin();
    }

    int findFirst() {
        pushDown();
        if (minCnt > 1) return l;
        if (l == r) return 0;
        right->pushDown();
        if (right->minCnt <= 1) return right->findFirst();
        left->pushDown();
        int ll = left->findFirst();
        if (ll != 0) return ll;
        return right->findFirst();
    }
};

struct coin {
    int x, y, index;
    bool operator < (const coin &that) const {
        return x < that.x;
    }
} a[N];

int n;
bool was[N];

node *build(int l, int r) {
    node *x = new node(l, r);
    if (l == r) {
        x->minV = a[l].y; x->minPos = l;
        x->minCnt = l;
        return x;
    }
    x->left = build(l, l + r >> 1);
    x->right = build((l + r >> 1) + 1, r);
    x->gatherMin(); x->gatherCnt();
    return x;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("DIVIDE.txt", "r", stdin);
#endif // ONLINE_JUDGE
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) a[i].index = i;
    sort(a + 1, a + 1 + n);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[i].y;
    node *root = build(1, n);
    for (int i = 1; i + i <= n; ++i) {
        int first = root->findFirst();
        int minValue = INF, minPos = 0;
        root->queryMin(first, minValue, minPos);
        ans -= minValue;
        root->decSuffix(minPos);
        root->erase(minPos);
        was[minPos] = 1;
    }
    cout << ans << '\n';
    stack<int> S;
    for (int i = 1; i <= n; ++i) {
        if (!was[i]) {
            S.push(a[i].index);
        } else {
            cout << S.top() << ' ' << a[i].index << '\n';
            S.pop();
        }
    }
    return 0;
}