## Submission #473107

# Submission time Handle Problem Language Result Execution time Memory
473107 2021-09-15T06:57:27 Z jwvg0425 Holiday (IOI14_holiday) C++17
100 / 100
782 ms 53616 KB
```#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using Pt = pair<i64, int>;

struct Node
{
int lidx, ridx;
Pt value;

Node() :value(Pt()), lidx(-1), ridx(-1) {}
};

Node node[2000005];

class PST
{

public:
class iterator
{
public:
iterator(PST& p, int n)
: pst(p), nx(n) {}

iterator& operator=(const iterator& other)
{
nx = other.nx;
return *this;
}

Pt get() const
{
return node[nx].value;
}

iterator left() const
{
return iterator(pst, node[nx].lidx);
}

iterator right() const
{
return iterator(pst, node[nx].ridx);
}

private:
PST& pst;
int nx;
};

template<typename M>
PST(int n_, const M& m) : n(n_), merge(m)
{
}

iterator it(int r)
{
return iterator(*this, root[r]);
}

int rmost() const
{
return n;
}

int update(int idx, const Pt& value)
{
return update((int)root.size() - 1, idx, value);
}

int update(int pre, int idx, const Pt& value)
{
root.emplace_back(_update(root[pre], idx, value, 0, n));
return (int)root.size() - 1;
}

Pt query(int k, int start, int end)
{
return _query(root[k], start, end, 0, n);
}

void init()
{
root.push_back(init(0, n));
}

private:
int init(int start, int end)
{
int idx = sz;
sz++;

if (start != end)
{
int mid = (start + end) / 2;

node[idx].lidx = init(start, mid);
node[idx].ridx = init(mid + 1, end);
}
return idx;
}

int _update(int prev, int idx, const Pt& value, int start, int end)
{
if (idx < start || idx > end)
return prev;

int nidx = sz;
sz++;

if (start == end)
node[nidx].value = value;
else
{
int mid = (start + end) / 2;
node[nidx].lidx = _update(node[prev].lidx, idx, value, start, mid);
node[nidx].ridx = _update(node[prev].ridx, idx, value, mid + 1, end);
node[nidx].value = merge(node[node[nidx].lidx].value, node[node[nidx].ridx].value);
}

return nidx;
}

Pt _query(int idx, int start, int end, int left, int right)
{
if (start <= left && right <= end)
return node[idx].value;

int mid = (left + right) / 2;

if (mid + 1 > end)
return _query(node[idx].lidx, start, end, left, mid);

if (mid < start)
return _query(node[idx].ridx, start, end, mid + 1, right);

return merge(_query(node[idx].lidx, start, end, left, mid),
_query(node[idx].ridx, start, end, mid + 1, right));
}

using Merge = function<Pt(const Pt&, const Pt&)>;
Merge merge;
vector<int> root;
int n;
int sz = 0;
};

int n, s, d;
auto tree = PST(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); });
vector<i64> arr;

i64 get(int l, int r)
{
int cnt = min(r - l + 1, d + 2 * l - r - s);

if (cnt <= 0)
return 0;

i64 res = 0;
auto lx = tree.it(l - 1);
auto rx = tree.it(r);

int s = 0, e = 100005;
int need = cnt;

while (need > 0)
{
if (s == e)
{
res += rx.get().xx - lx.get().xx;
break;
}

int m = (s + e) / 2;
auto lr = lx.right();
auto rr = rx.right();

if (rr.get().yy - lr.get().yy >= need)
{
lx = lr;
rx = rr;
s = m + 1;
continue;
}

need -= rr.get().yy - lr.get().yy;
res += rr.get().xx - lr.get().xx;
lx = lx.left();
rx = rx.left();
e = m;
}

return res;
}

i64 big[100005];

void f(int y1, int y2, int x1, int x2)
{
if (y1 > y2 || x1 > x2)
return;

i64 ans = -(1ll << 60);
i64 ansp = x1;

int y = (y1 + y2) / 2;

for (int i = x1; i <= x2; i++)
{
i64 v = get(y, i);
if (v > ans)
{
ans = v;
ansp = i;
}
}

big[y] = ans;

f(y1, y - 1, x1, ansp);
f(y + 1, y2, ansp, x2);
}

i64 solve()
{
for (int i = 0; i < n; i++)
big[i] = -(1ll << 60);

vector<ii64> byVal;
for (int i = 0; i < n; i++)
byVal.emplace_back(arr[i], i);

sort(all(byVal));

vector<int> order(n);
for (int i = 0; i < n; i++)
order[byVal[i].yy] = i + 1;

tree = PST(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); });
tree.init();

for (int i = 0; i < n; i++)
tree.update(order[i], Pt(arr[i], 1));

f(1, s, 1, n);

i64 ans = big[1];

for (int i = 1; i <= n; i++)
ans = max(ans, big[i]);

return ans;
}

long long int findMaxAttraction(int n_, int s_, int d_, int attraction[])
{
n = n_;
s = s_ + 1;
d = d_;

arr.resize(n);
for (int i = 0; i < n; i++)
arr[i] = attraction[i];

i64 ans = solve();
reverse(all(arr));
s = n + 1 - s;

i64 ans2 = solve();

return max(ans, ans2);
}```

### Compilation message

```holiday.cpp: In constructor 'Node::Node()':
holiday.cpp:31:5: warning: 'Node::value' will be initialized after [-Wreorder]
31 |  Pt value;
|     ^~~~~
holiday.cpp:30:6: warning:   'int Node::lidx' [-Wreorder]
30 |  int lidx, ridx;
|      ^~~~
holiday.cpp:33:2: warning:   when initialized here [-Wreorder]
33 |  Node() :value(Pt()), lidx(-1), ridx(-1) {}
|  ^~~~
holiday.cpp: In instantiation of 'PST::PST(int, const M&) [with M = <lambda(const Pt&, const Pt&)>]':
holiday.cpp:172:94:   required from here
holiday.cpp:167:6: warning: 'PST::n' will be initialized after [-Wreorder]
167 |  int n;
|      ^
holiday.cpp:165:8: warning:   'PST::Merge PST::merge' [-Wreorder]
165 |  Merge merge;
|        ^~~~~
holiday.cpp:75:2: warning:   when initialized here [-Wreorder]
75 |  PST(int n_, const M& m) : n(n_), merge(m)
|  ^~~
holiday.cpp: In instantiation of 'PST::PST(int, const M&) [with M = solve()::<lambda(const Pt&, const Pt&)>]':
holiday.cpp:262:90:   required from here
holiday.cpp:167:6: warning: 'PST::n' will be initialized after [-Wreorder]
167 |  int n;
|      ^
holiday.cpp:165:8: warning:   'PST::Merge PST::merge' [-Wreorder]
165 |  Merge merge;
|        ^~~~~
holiday.cpp:75:2: warning:   when initialized here [-Wreorder]
75 |  PST(int n_, const M& m) : n(n_), merge(m)
|  ^~~```

#### Subtask #1 7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47564 KB Output is correct
2 Correct 25 ms 47520 KB Output is correct
3 Correct 23 ms 47596 KB Output is correct
4 Correct 24 ms 47604 KB Output is correct
5 Correct 24 ms 47644 KB Output is correct
6 Correct 24 ms 47620 KB Output is correct
7 Correct 24 ms 47564 KB Output is correct

#### Subtask #2 23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 53616 KB Output is correct
2 Correct 124 ms 53560 KB Output is correct
3 Correct 334 ms 53612 KB Output is correct
4 Correct 428 ms 53528 KB Output is correct
5 Correct 365 ms 53276 KB Output is correct
6 Correct 102 ms 49240 KB Output is correct
7 Correct 188 ms 50644 KB Output is correct
8 Correct 232 ms 51092 KB Output is correct
9 Correct 73 ms 48892 KB Output is correct

#### Subtask #3 17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47792 KB Output is correct
2 Correct 30 ms 47820 KB Output is correct
3 Correct 30 ms 47776 KB Output is correct
4 Correct 35 ms 47736 KB Output is correct
5 Correct 32 ms 47820 KB Output is correct
6 Correct 27 ms 47672 KB Output is correct
7 Correct 28 ms 47692 KB Output is correct
8 Correct 27 ms 47596 KB Output is correct
9 Correct 27 ms 47608 KB Output is correct

#### Subtask #4 53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 53564 KB Output is correct
2 Correct 311 ms 53528 KB Output is correct
3 Correct 170 ms 50400 KB Output is correct
4 Correct 32 ms 47820 KB Output is correct
5 Correct 28 ms 47708 KB Output is correct
6 Correct 27 ms 47656 KB Output is correct
7 Correct 27 ms 47704 KB Output is correct
8 Correct 776 ms 53608 KB Output is correct
9 Correct 782 ms 53528 KB Output is correct