-
Notifications
You must be signed in to change notification settings - Fork 159
Expand file tree
/
Copy pathparallel_binary_search.cc
More file actions
149 lines (137 loc) · 4.08 KB
/
parallel_binary_search.cc
File metadata and controls
149 lines (137 loc) · 4.08 KB
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
//
// Parallel Binary Search
//
// Description:
//
// Let W(t) be a data structure depending on time t.
// Suppose that there are n agents. Each agent j wants to
// find the smallest time t(j) such that cond(j, W(t(j))) == true
// where cond(j, W(t)) is monotone in t.
//
// If we perform n binary searches independently, we will construct
// W(t) multiple times. Thus, we avoid the redundant construction
// by performing n binary searches in parallel. Imagine a binary
// search tree on t. For each node, we first construct W(t).
// Then we process multiple agents in parallel. Then, the total
// number of constructions is O(log T), which is independent to
// the number of agents.
//
// Complexity:
//
// Suppose that W(t) is constructed from W(t') in time M(|t-t'|),
// and the condition cond(j,W(t)) is evaluated in time Q.
// Then, it runs in O(M(T log T) + n Q log T) time.
//
// Even if W does not have decremental operations, i.e., W(t)
// cannot be constructed from W(t') with t' > t, we can still use
// the parallel binary search that runs in O(M(T) log T + n Q log T);
// time. The constant factor is twice worse than the above.
// Similar result holds if W does not have incremental operations.
//
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }
using Int = __int128_t;
// Point Query, Range Update
template <class T>
struct FenwickTree {
vector<T> x;
FenwickTree(int n) : x(n) { }
void add(int k, T a) { // aux
for (; k < x.size(); k |= k+1) x[k] += a;
}
void add(int i, int j, T a) { // add x[k] += a for all k in [i,j]
add(i, a);
if (j+1 < x.size()) add(j+1, -a);
}
T get(int k) { // return x[k]
T sum = 0;
for (; k >= 0; k = (k&(k+1))-1) sum += x[k];
return sum;
}
};
template <class Update, class Cond>
vector<int> parallelBinarySearch(
int n, int lo, int hi, Update update, Cond cond) {
using It = vector<int>::iterator;
vector<int> agents(n), solution(n, lo);
iota(all(agents), 0);
It begin = agents.begin(), end = agents.end();
deque<tuple<int,int,It,It>> stack = {make_tuple(lo, hi, begin, end)};
while (!stack.empty()) {
// invariant: elems in [begin, end) satisfy "!cond(lo) and cond(hi)"
tie(lo, hi, begin, end) = stack.back();
stack.pop_back();
if (begin == end) continue;
if (lo+1 == hi) {
for_each(begin, end, [&](int k) { solution[k] = hi; });
continue;
}
int mi = (lo + hi) / 2;
update(mi);
It mid = partition(begin, end, [&](int k) { return cond(k); });
stack.push_back(make_tuple(mi, hi, mid, end));
stack.push_back(make_tuple(lo, mi, begin, mid));
}
return solution;
}
void SPOJ_METEORS() {
int n, m, k;
scanf("%d %d", &n, &m);
vector<vector<int>> S(n);
vector<Int> p(n);
for (int i = 0; i < m; ++i) {
int j; scanf("%d", &j);
S[j-1].push_back(i);
}
for (int i = 0; i < n; ++i)
scanf("%lld", &p[i]);
scanf("%d", &k);
vector<int> l(k), r(k);
vector<Int> a(k);
for (int i = 0; i < k; ++i) {
scanf("%d %d %lld", &l[i], &r[i], &a[i]);
--l[i]; --r[i];
}
FenwickTree<Int> FT(m);
int curr = -1;
auto update = [&](int time) {
while (curr < time) {
++curr;
if (l[curr] <= r[curr]) {
FT.add(l[curr], r[curr], a[curr]);
} else {
FT.add(l[curr], m-1, a[curr]);
FT.add(0, r[curr], a[curr]);
}
}
while (curr > time) {
if (l[curr] <= r[curr]) {
FT.add(l[curr], r[curr], -a[curr]);
} else {
FT.add(l[curr], m-1, -a[curr]);
FT.add(0, r[curr], -a[curr]);
}
--curr;
}
};
// minimum time such that cond = true.
auto cond = [&](int j) {
Int total = 0;
for (int i: S[j]) {
total += FT.get(i);
}
return total >= p[j];
};
auto solution = parallelBinarySearch(n, -1, k, update, cond);
for (int i = 0; i < n; ++i) {
if (solution[i] >= k) cout << "NIE" << endl;
else cout << 1+solution[i] << endl;
}
}
int main() {
SPOJ_METEORS();
}