# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
871766 |
2023-11-11T14:02:15 Z |
LOLOLO |
Holiday (IOI14_holiday) |
C++17 |
|
677 ms |
18764 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 4e6 + 100;
pair <ll, ll> seg[N];
int n;
void upd(int id, int l, int r, int x, int v, int add) {
if (l > x || r < x)
return;
if (l == r) {
seg[id].f += v;
seg[id].s += add;
return;
}
int m = (l + r) / 2;
upd(id * 2, l, m, x, v, add);
upd(id * 2 + 1, m + 1, r, x, v, add);
seg[id].f = seg[id * 2].f + seg[id * 2 + 1].f;
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
}
ll get(int id, int l, int r, ll cnt) {
if (seg[id].f <= cnt)
return seg[id].s;
if (l == r) {
return min((seg[id].s / seg[id].f) * cnt, seg[id].s);
}
int m = (l + r) / 2;
if (seg[id * 2 + 1].f >= cnt)
return get(id * 2 + 1, m + 1, r, cnt);
return get(id * 2, l, m, cnt - seg[id * 2 + 1].f) + seg[id * 2 + 1].s;
}
int L, R;
vector <int> v, rnk;
void move(int l, int r) {
while (L < l) {
upd(1, 0, n - 1, rnk[L], -1, -v[L]);
L++;
}
while (L > l) {
L--;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
}
while (R < r) {
R++;
upd(1, 0, n - 1, rnk[R], 1, v[R]);
}
while (R > r) {
upd(1, 0, n - 1, rnk[R], -1, -v[R]);
R--;
}
}
ll cal(int v) {
if (v < 0)
return 0;
return get(1, 1, n, v);
}
void maximize(pair <ll, ll> &a, pair <ll, ll> b) {
if (a.f < b.f) {
a = b;
} else {
if (a.f == b.f) {
a.s = min(a.s, b.s);
}
}
}
void dnc(int st, int l1, int r1, int l, int r, vector <pair <ll, ll>> &f) {
if (l1 > r1 || st < 0)
return;
int m1 = (l1 + r1) / 2;
for (int i = l; i <= r; i++) {
move(min(st, i), max(st, i));
ll v = cal(m1 - abs(i - st));
maximize(f[m1], {v, abs(i - st)});
}
int opt = f[m1].s;
if (r >= st && l >= st) {
dnc(st, l1, m1 - 1, l, opt + st, f);
dnc(st, m1 + 1, r1, opt + st, r, f);
} else {
dnc(st, m1 + 1, r1, l, st - opt, f);
dnc(st, l1, m1 - 1, st - opt, r, f);
}
}
ll findMaxAttraction(int _n, int st, int d, int att[]) {
n = _n;
map <int, int> mp;
int timer = 0;
for (int i = 0; i < n; i++) {
v.pb(att[i]);
mp[att[i]];
}
for (auto &x : mp) {
x.s = timer;
timer++;
}
for (auto x : v)
rnk.pb(mp[x]);
L = R = 0;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
vector <pair <ll, ll>> d1(d + 1, {0, 0}), d2(d + 1, {0, 0});
dnc(st, 0, d, st, n - 1, d1);
dnc(st - 1, 0, d, 0, st - 1, d2);
ll ans = d1[d].f;
for (int i = 0; i < d; i++) {
auto t = d1[i];
int v = t.s + 1;
if (v + i <= d) {
ans = max(ans, t.f + d2[d - v - i].f);
}
t = d2[i];
v = t.s + 2;
if (v + i <= d) {
ans = max(ans, t.f + d1[d - v - i].f);
}
}
for (int i = st; i >= 0; i--) {
move(i, st);
int v = st - i;
if (v <= d) {
ans = max(ans, cal(d - v));
}
}
return ans;
}
/*int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int att[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 100000};
cout << findMaxAttraction(10, 4, 7, att) << '\n';
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
836 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
10088 KB |
Output is correct |
2 |
Correct |
372 ms |
10088 KB |
Output is correct |
3 |
Correct |
427 ms |
10088 KB |
Output is correct |
4 |
Correct |
374 ms |
10068 KB |
Output is correct |
5 |
Correct |
434 ms |
7840 KB |
Output is correct |
6 |
Correct |
142 ms |
8796 KB |
Output is correct |
7 |
Correct |
227 ms |
6208 KB |
Output is correct |
8 |
Correct |
280 ms |
6176 KB |
Output is correct |
9 |
Correct |
92 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
1368 KB |
Output is correct |
2 |
Correct |
8 ms |
1116 KB |
Output is correct |
3 |
Correct |
11 ms |
1380 KB |
Output is correct |
4 |
Correct |
11 ms |
1116 KB |
Output is correct |
5 |
Correct |
10 ms |
1116 KB |
Output is correct |
6 |
Correct |
3 ms |
956 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
3 ms |
912 KB |
Output is correct |
9 |
Correct |
3 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
461 ms |
11648 KB |
Output is correct |
2 |
Correct |
614 ms |
18764 KB |
Output is correct |
3 |
Correct |
263 ms |
5840 KB |
Output is correct |
4 |
Correct |
10 ms |
1116 KB |
Output is correct |
5 |
Correct |
3 ms |
920 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
3 ms |
856 KB |
Output is correct |
8 |
Correct |
677 ms |
12876 KB |
Output is correct |
9 |
Correct |
675 ms |
12616 KB |
Output is correct |