-
Notifications
You must be signed in to change notification settings - Fork 0
/
2517_indexTree.cpp
107 lines (92 loc) · 2.06 KB
/
2517_indexTree.cpp
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <vector>
#include <queue>
#define SPEED first
#define ORDER second
using namespace std;
class IndexTree
{
public:
int leafLeft;
int treeSize;
vector<int> v_tree;
IndexTree(int N)
{
for (leafLeft = 1; leafLeft < N; leafLeft *= 2)
;
treeSize = leafLeft * 2;
v_tree.resize(treeSize);
}
int logicFun(int num1, int num2)
{
return num1 + num2;
}
void updateTree(int index)
{
if (index == 0)
return;
v_tree[index] = logicFun(v_tree[2 * index], v_tree[2 * index + 1]);
updateTree(index / 2);
}
void add(int order)
{
int index = leafLeft + order - 1;
v_tree[index]++;
updateTree(index / 2);
}
int query(int begin, int end)
{
int L = leafLeft + begin - 1;
int R = leafLeft + end - 1;
int result = 0;
while (L < R)
{
int nextL = (L + 1) / 2;
int nextR = (R - 1) / 2;
if (nextL != L / 2)
result = logicFun(result, v_tree[L]);
if (nextR != R / 2)
result = logicFun(result, v_tree[R]);
L = nextL;
R = nextR;
}
if (L == R)
result = logicFun(result, v_tree[L]);
return result;
}
};
int N;
vector<int> v_speed;
priority_queue<pair<int, int>> pq_runner;
vector<int> v_rank;
void solution()
{
cin >> N;
v_speed.resize(N + 1);
v_rank.resize(N + 1);
for (int i = 1; i <= N; i++)
{
int speed;
cin >> speed;
pq_runner.push(make_pair(speed, i));
}
IndexTree indexTreeCount(N);
while (!pq_runner.empty())
{
auto runner = pq_runner.top();
pq_runner.pop();
v_rank[runner.ORDER] = indexTreeCount.query(1, runner.ORDER) + 1;
indexTreeCount.add(runner.ORDER);
}
for (int i = 1; i <= N; i++)
{
cout << v_rank[i] << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solution();
return 0;
}