#include <bits/stdc++.h>
#include"holiday.h"
#define pb push_back
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << (x) << "\n"
#else
#define debug(x)
#endif
struct SegTree
{
int n;
vector<int> left, right;
vector<long long int> data;
SegTree(int n) : n(n), left(1, -1), right(1, -1), data(1, 0) {}
void expand(int index)
{
if (left[index] != -1)
return;
left[index] = data.size();
left.pb(-1), right.pb(-1), data.pb(0);
right[index] = data.size();
left.pb(-1), right.pb(-1), data.pb(0);
}
void change(int l, int r, int index, int i, int val)
{
if (i >= r || l > i)
return;
if (l + 1 == r)
{
data[index] += val;
return;
}
expand(index);
int m = l+r>>1;
change(l, m, left[index], i, val);
change(m, r, right[index], i, val);
data[index] = data[left[index]] + data[right[index]];
}
void change(int i, int val) { change(0, n, 0, i, val); }
long long int get(int l, int r, int index, int ss, int ee)
{
if (ss >= r || l >= ee || index == -1)
return 0;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
long long int lres = get(l, m, left[index], ss, ee);
long long int rres = get(m, r, right[index], ss, ee);
return lres + rres;
}
long long int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};
int *v;
int n;
int start;
int d;
constexpr static int MXSIZE1 = 1e9 + 1;
long long int subtask1()
{
SegTree st1(MXSIZE1);
SegTree st2(MXSIZE1);
long long int best = 0;
for (int l = start; l >= 0; l--)
{
for (int r = start; r < n; r++)
{
st1.change(v[r], 1);
st2.change(v[r], v[r]);
int remaining = d - (r - l) - min(start - l, r - start);
int ll = -1, rr = MXSIZE1;
while (rr - ll > 1)
{
int m = ll+rr>>1;
if (st1.get(m, MXSIZE1) < remaining)
rr = m;
else
ll = m;
}
if (l == 0 && r == 3)
debug(rr);
long long int sum = st2.get(rr, MXSIZE1);
if (rr != 0)
{
long long int leftover = remaining - st1.get(rr, MXSIZE1);
sum += leftover * (rr - 1);
}
debug(sum);
best = max(best, sum);
}
for (int r = start; r < n; r++)
{
st1.change(v[r], -1);
st2.change(v[r], -v[r]);
}
if (l > 0)
{
st1.change(v[l-1], 1);
st2.change(v[l-1], v[l-1]);
}
}
return best;
}
constexpr static int MXSIZE = 101;
long long int subtask2()
{
SegTree st1(MXSIZE);
SegTree st2(MXSIZE);
long long int best = 0;
for (int i = 0; i < n && i < d; i++)
{
st1.change(v[i], 1);
st2.change(v[i], v[i]);
int l = -1, r = MXSIZE;
while (r - l > 1)
{
int m = l+r>>1;
if (st1.get(m, MXSIZE) + i < d)
r = m;
else
l = m;
}
long long int sum = st2.get(r, MXSIZE);
if (r != 0)
{
long long int remaining = d - st1.get(r, MXSIZE) - i;
sum += remaining * (r-1);
}
best = max(best, sum);
}
return best;
}
long long int findMaxAttraction(int nn, int sstart, int dd, int aattraction[]) {
n = nn;
start = sstart;
d = dd;
v = aattraction;
int mx = 0;
for (int i = 0; i < n; i++)
mx = max(mx, v[i]);
if (mx <= 100)
return subtask2();
return subtask1();
}
Compilation message
holiday.cpp: In member function 'void SegTree::change(int, int, int, int, int)':
holiday.cpp:37:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int m = l+r>>1;
| ~^~
holiday.cpp: In member function 'long long int SegTree::get(int, int, int, int, int)':
holiday.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = l+r>>1;
| ~^~
holiday.cpp: In function 'long long int subtask1()':
holiday.cpp:81:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int m = ll+rr>>1;
| ~~^~~
holiday.cpp: In function 'long long int subtask2()':
holiday.cpp:126:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int m = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
740 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
596 KB |
Output is correct |
| 2 |
Correct |
26 ms |
688 KB |
Output is correct |
| 3 |
Correct |
28 ms |
596 KB |
Output is correct |
| 4 |
Correct |
26 ms |
596 KB |
Output is correct |
| 5 |
Correct |
31 ms |
688 KB |
Output is correct |
| 6 |
Correct |
9 ms |
596 KB |
Output is correct |
| 7 |
Correct |
16 ms |
700 KB |
Output is correct |
| 8 |
Correct |
24 ms |
596 KB |
Output is correct |
| 9 |
Correct |
7 ms |
696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
688 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4520 KB |
Output is correct |
| 4 |
Execution timed out |
5062 ms |
4292 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
676 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
