TLE求助

#include <iostream>
#include <cstdio>
#include <chrono>
#include <random>
#include <ctime>

using namespace std;

inline int RD() {
    int x = 0, f = 1;
    char ch = getchar();
    
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') 
        x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

inline void WT(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) WT(x / 10);
    putchar(x % 10 + '0');
    return;
}

const int N = 1e6 + 5;

#define FI first
#define SE second
#define PII pair<int, int>
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

int sz[N], rd[N], val[N], ls[N], rs[N], R;
int n, m, node, cnt = 1;
bool vis[N];
PII p[N];

int nd(int v) {
    int x = ++node;
    return sz[x] =  1, val[x] = v, rd[x] = rand(), x;
}

void push(int x) { sz[x] = sz[ls[x]] + sz[rs[x]] + 1; }

void spl(int p, int v, int &x, int &y) {
    if (!p) return x = y = 0, void();
    if (v <= sz[ls[p]]) spl(ls[p], v, x, ls[y = p]);
    else spl(rs[p], v - sz[ls[p]] - 1, rs[x = p], y);
    push(p);
}

int mer(int x, int y) {
    if (!x || !y) return x | y;
    if (rd[x] > rd[y]) return rs[x] = mer(rs[x], y), push(x), x;
    else return ls[y] = mer(x, ls[y]), push(y), y;
}

void pr(int p) {
    if (!p) return;
    pr(ls[p]);

    if (val[p]) WT(val[p]), putchar(' ');
    else {
        while (vis[cnt]) cnt++;
        WT(cnt), putchar(' ');
        vis[cnt] = true;
    }
    
    pr(rs[p]);
}

int main() {
    srand(19260817);
    n = RD(), m = RD();
    LF(i, 1, n) R = mer(R, nd(0));
    LF(i, 1, m) p[i].FI = RD(), p[i].SE = RD();
    
    RF(i, m, 1) {
        int x, y, z;
        spl(R, 1, x, y), spl(y, p[i].SE - 1, y, z);

        if (val[x] != p[i].FI && (val[x] || vis[p[i].FI])) {
            puts("-1");
            return 0;
        }

        val[x] = p[i].FI;
        R = mer(mer(y, x), z);
        vis[p[i].FI] = true;
    }

    pr(R);
    return 0;
}