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
/* 
 * PRA
 * Autor: Szymon Tur
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> utemp;

void quicksortv(int left, int right)
{
if (left<right)
{
int m=left;
for (int i=left+1;i<=right;i++)
{
if (lexicographical_compare(utemp[i].begin(),utemp[i].end(),utemp[left].begin(),utemp[left].end())) swap(utemp[++m],utemp[i]);
}
swap(utemp[left],utemp[m]);
quicksortv(left,m-1);
quicksortv(m+1,right);
}
}

int main()
{
vector<int> t;
int n,m,x;
cin >> n >> m;
for (int i=0;i<n;i++)
{
cin >> x;
t.push_back(x);
}
t.push_back(1);
utemp.push_back(t);
int nt, te;
for (int i=1;i<m;i++)
{
cin >> nt >> te;
t[n] = i+1;
t[nt-1] = te;
utemp.push_back(t);
}
quicksortv(0,m-1);
for (int i=0;i<m;i++)
cout << utemp[i][n] << " ";
return 0;
}