1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, m, maxval = 0;
    cin>>n>>m;//temp, children
    int** answers = new int*[m];
    for (int i = 0; i < m; i++) {
        answers[i] = new int[n+1];
    }
    for (int i = 0; i < n; i++) {
        cin>>answers[0][i];
        if (answers[0][i] > maxval)
            maxval = answers[0][i];
    }
    answers[0][n] = 1;
    for (int i = 1; i < m; i++) {
        copy(answers[i-1], answers[i-1]+n+1, answers[i]);
        answers[i][n] = i+1;
        int a, b;
        cin>>a>>b;
        answers[i][a-1] = b;
        if (b > maxval)
            maxval = b;
    }
    if (m > maxval)
        maxval = m;
    maxval++;

    int** persistedAnswers = new int*[m];
    for (int i = 0; i < m; i++) {
        persistedAnswers[i] = new int[n+1];
    }

    for (int i = 0; i < m; i++) {
        copy(answers[i], answers[i]+n+1, persistedAnswers[i]);
    }

    int *numbersList = new int[maxval];
    fill(numbersList, numbersList+maxval, 0);
    int** outputList = new int*[m];
    for (int i = 0; i < m; i++) {
        outputList[i] = new int[n+1];
    }
    int digitBuffer;

    for (int j = n; j > -1; j--) {
        for (int i = 0; i < m; i++) {
            numbersList[answers[i][j]]++;
        }

        for (int i = 1; i < maxval; i++) {
            numbersList[i] += numbersList[i - 1];
        }

        for (int i = m - 1; i > -1; i--) {
            digitBuffer = answers[i][j];
            numbersList[digitBuffer]--;
            for (int k = 0; k < n+1; k++) {
                outputList[numbersList[digitBuffer]][k] = answers[i][k];
            }
        }
        for (int l = 0; l < m; l++) {
            copy(outputList[l], outputList[l]+n+1, answers[l]);
        }
        fill(numbersList, numbersList+maxval, 0);
    }

    for (int i = 0; i < m; i++) {
        cout<<outputList[i][n]<<" ";
    }

    return 0;
}