#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#define nl "\n"
// making some things easily accessible
// push_back pop_back emplace_back make_pair lower_bound upper_bound reserve resize reverse
const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
struct segt {
int tl;
vector<big> t;
void init(int l, big val) {
tl = l;
t = vector<big>(tl << 2, val);
}
big task(big child1, big child2) {
return child1 + child2;
}
void update(int node, int l, int r, int pos, big val) {
if(l == r) {
t[node] = val;
} else {
int mid = (l + r) >> 1;
if(pos <= mid) {
update(node << 1, l, mid, pos, val);
} else {
update((node << 1) + 1, mid + 1, r, pos, val);
}
t[node] = task(t[node << 1], t[(node << 1) + 1]);
}
}
void update(int pos, big val) {
update(1, 0, tl - 1, pos, val);
}
big query(int node, int l, int r, int lq, int rq) {
if(lq > rq) {
return 0;
} else if(lq <= l && rq >= r) {
return t[node];
} else {
int mid = (l + r) >> 1;
return task(query(node << 1, l, mid, lq, min(rq, mid)), query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
}
}
big query(int lq, int rq) {
return query(1, 0, tl - 1, lq, rq);
}
void build(vector<pii>& v, int node, int l, int r) {
if(l == r) {
t[node] = v[l].fe;
} else {
int mid = (l + r) >> 1;
build(v, node << 1, l, mid);
build(v, (node << 1) + 1, mid + 1, r);
t[node] = task(t[node << 1], t[(node << 1) + 1]);
}
}
void build(vector<pii>& v) {
build(v, 1, 0, tl - 1);
}
};
struct countt {
int tl;
vector<int> t;
void init(int l, int val) {
tl = l;
t = vector<int>(tl << 2, val);
}
int task(int child1, int child2) {
return child1 + child2;
}
void update(int node, int l, int r, int pos, int val) {
if(l == r) {
t[node] = val;
} else {
int mid = (l + r) >> 1;
if(pos <= mid) {
update(node << 1, l, mid, pos, val);
} else {
update((node << 1) + 1, mid + 1, r, pos, val);
}
t[node] = task(t[node << 1], t[(node << 1) + 1]);
}
}
void update(int pos, int val) {
update(1, 0, tl - 1, pos, val);
}
int query(int node, int l, int r, int v) {
if(l == r) {
return l;
} else {
int mid = ((l + r) >> 1);
if(t[node << 1] >= v) {
return query(node << 1, l, mid, v);
} else {
return query((node << 1) + 1, mid + 1, r, v - t[node << 1]);
}
}
}
int query(int v) {
return query(1, 0, tl - 1, v);
}
void build(vector<int>& v, int node, int l, int r) {
if(l == r) {
t[node] = v[l];
} else {
int mid = (l + r) >> 1;
build(v, node << 1, l, mid);
build(v, (node << 1) + 1, mid + 1, r);
t[node] = task(t[node << 1], t[(node << 1) + 1]);
}
}
void build(vector<int>& v) {
build(v, 1, 0, tl - 1);
}
};
int n, d, sp;
vector<int> rmap;
vector<big> dp;
segt st;
countt ct;
vector<big> vals;
int L, R;
void cf(int l, int r) {
while(R < r) {
R++;
ct.update(rmap[R], 1);
st.update(rmap[R], vals[rmap[R]]);
}
while(L > l) {
L--;
ct.update(rmap[L], 1);
st.update(rmap[L], vals[rmap[L]]);
}
while(L < l) {
ct.update(rmap[L], 0);
st.update(rmap[L], 0);
L++;
}
while(R > r) {
ct.update(rmap[R], 0);
st.update(rmap[R], 0);
R--;
}
}
void f(int l, int r, int o_l, int o_r) {
if(l > r) {
return;
}
int mid = ((r - l) >> 1) + l;
big ans = -1;
int o = 0;
fr(i, o_l, o_r + 1) {
cf(i, mid);
int len = mid - i + 1;
int dist = mid - i + min(mid - sp, sp - i);
int rem = d - dist;
if(rem > len) {
rem = len;
}
big temp = st.query(0, ct.query(rem));
if(temp > ans) {
ans = temp;
o = i;
}
}
dp[mid] = ans;
f(l, mid - 1, o_l, o);
f(mid + 1, r, o, o_r);
}
big findMaxAttraction(int N, int start, int D, int attraction[5]) {
n = N;
sp = start;
d = D;
rmap.resize(n, 0);
dp.resize(n, -1);
vals.resize(n, 0);
vector<pii> aux(n);
fr(i, 0, n) {
aux[i] = make_pair(attraction[i], i);
}
sort(aux.begin(), aux.end());
reverse(aux.begin(), aux.end());
fr(i, 0, n) {
vals[i] = aux[i].fe;
rmap[aux[i].se] = i;
}
st.init(n, 0);
ct.init(n, 0);
L = sp;
R = sp;
ct.update(rmap[sp], 1);
st.update(rmap[sp], vals[rmap[sp]]);
f(sp, n - 1, 0, sp);
big ans = -1;
fr(i, 0, n) {
ans = max(ans, dp[i]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
153 ms |
8340 KB |
Output is correct |
| 3 |
Correct |
153 ms |
8304 KB |
Output is correct |
| 4 |
Correct |
154 ms |
8388 KB |
Output is correct |
| 5 |
Correct |
219 ms |
7724 KB |
Output is correct |
| 6 |
Correct |
54 ms |
2824 KB |
Output is correct |
| 7 |
Correct |
112 ms |
4620 KB |
Output is correct |
| 8 |
Correct |
141 ms |
5452 KB |
Output is correct |
| 9 |
Correct |
36 ms |
2228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
844 KB |
Output is correct |
| 2 |
Correct |
2 ms |
844 KB |
Output is correct |
| 3 |
Correct |
3 ms |
936 KB |
Output is correct |
| 4 |
Correct |
8 ms |
816 KB |
Output is correct |
| 5 |
Correct |
10 ms |
892 KB |
Output is correct |
| 6 |
Correct |
2 ms |
716 KB |
Output is correct |
| 7 |
Correct |
3 ms |
716 KB |
Output is correct |
| 8 |
Correct |
3 ms |
760 KB |
Output is correct |
| 9 |
Correct |
3 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8396 KB |
Output is correct |
| 2 |
Correct |
162 ms |
8412 KB |
Output is correct |
| 3 |
Correct |
327 ms |
4428 KB |
Output is correct |
| 4 |
Correct |
13 ms |
844 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
716 KB |
Output is correct |
| 7 |
Correct |
3 ms |
680 KB |
Output is correct |
| 8 |
Correct |
743 ms |
8840 KB |
Output is correct |
| 9 |
Correct |
837 ms |
8908 KB |
Output is correct |
