#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define pii pair<ll, int>
#define mt make_tuple
//pii has ll for now b/c whatever
#define maxn 100010
vector<pii> stuff;
int n;
int d;
int nums[maxn]; //stores how many attractions are at each index
int indo[maxn]; //stores my index in sorted list
ll segsum[maxn*4];
int segct[maxn*4]; //we will only need to activate and deactivate values
ll unor[maxn]; //only go to this spot once
int unospotr[maxn];
ll dosr[maxn]; //go to this spot and back
int dosspotr[maxn];
ll unol[maxn]; //only go to this spot once
int unospotl[maxn];
ll dosl[maxn]; //go to this spot and back
int dosspotl[maxn];
#define ti tuple<int, int, int, int>
ll query(int amount, int ss = 0, int se = n-1, int si = 0) {
if (amount <= 0) return 0;
if (ss == se) return segsum[si];
int numleft = segct[si*2+1];
int mid = (ss+se)/2;
if (numleft >= amount) {
return query(amount, ss, mid, si*2+1);
}
else {
return segsum[si*2+1] + query(amount - numleft, mid+1, se, si*2+2);
}
}
void addval(int ii, int ss = 0, int se = n-1, int si = 0) {
if (ss == se) {
if (segct[si] == 0) {
segct[si] = 1;
// cout << "guy: " << stuff[ss].first << endl;
segsum[si] += stuff[ss].first;
// cout << "lo: " << segsum[si] << endl;
}
return;
}
int mid = (ss+se)/2;
if (ii <= mid) {
addval(ii, ss, mid, si*2+1);
}
else addval(ii, mid+1, se, si*2+2);
segct[si] = segct[si*2+1] + segct[si*2+2];
segsum[si] = segsum[si*2+1] + segsum[si*2+2];
}
ll findMaxAttraction(int nn, int start, int dd, int attraction[]) {
fill(unor, unor+maxn, -1);
fill(dosr, dosr+maxn, -1);
fill(unol, unol+maxn, -1);
fill(dosl, dosl+maxn, -1);
n = nn;
d = dd;
for (int i = 0; i < n; i++) {
nums[i] = attraction[i];
// cout << "num " << i << " :: " << nums[i] << endl;
stuff.push_back(pii(nums[i], i));
}
sort(stuff.begin(), stuff.end());
reverse(stuff.begin(), stuff.end());
for (int i = 0; i < n; i++) {
indo[stuff[i].second] = i;
}
// cout << "here" << endl;
//first we shall go to the right
vector<ti> rn; //ranges
//the setup is the first value is how much "d" is allocated
// the second value is the leftmost guy that checks for me
// the third is the rightmost guy that checks for me
rn.push_back(mt(start, n-1, 0, d));
while (rn.size()) {
fill(segsum, segsum+n*4, 0);
fill(segct, segct+n*4, 0);
vector<ti> nrn;
int mproc = start;
for (ti val : rn) {
//keep them sorted from left to right
int mc = get<0>(val);
int me = get<1>(val);
int qs = get<2>(val);
int qe = get<3>(val);
int place = (qs + qe)/2;
for (int i = mproc; i < mc; i++) addval(indo[i]);
for (int i = mc; i <= me; i++) {
addval(indo[i]);
int numleft = place - (i - start);
ll cur = query(numleft);
// cout << "cur: " << cur << endl;
if (cur > unor[place]) {
unor[place] = cur;
unospotr[place] = i;
}
}
mproc = me+1;
//push back qs to place-1 and place+1 to qe
if (place-1 >= qs) nrn.push_back(mt(mc, unospotr[place], qs, place-1));
if (place+1 <= qe) nrn.push_back(mt(unospotr[place], me, place+1, qe));
}
rn.clear();
for (ti thing : nrn) rn.push_back(thing);
}
//TEST ABOVE GUY BEFORE DOING ANYTHING ELSE (e.g. tons of copy paste)
rn.push_back(mt(start, n-1, 0, d));
while (rn.size()) {
fill(segsum, segsum+n*4, 0);
fill(segct, segct+n*4, 0);
vector<ti> nrn;
int mproc = start;
for (ti val : rn) {
//keep them sorted from left to right
int mc = get<0>(val);
int me = get<1>(val);
int qs = get<2>(val);
int qe = get<3>(val);
int place = (qs + qe)/2;
for (int i = mproc; i < mc; i++) addval(indo[i]);
for (int i = mc; i <= me; i++) {
addval(indo[i]);
int numleft = place - 2*(i - start);
ll cur = query(numleft);
// cout << "cur: " << cur << endl;
if (cur > dosr[place]) {
dosr[place] = cur;
dosspotr[place] = i;
}
}
mproc = me+1;
//push back qs to place-1 and place+1 to qe
if (place-1 >= qs) nrn.push_back(mt(mc, dosspotr[place], qs, place-1));
if (place+1 <= qe) nrn.push_back(mt(dosspotr[place], me, place+1, qe));
}
rn.clear();
for (ti thing : nrn) rn.push_back(thing);
}
//there will be 4 of the above loops (yikes, but should be all similar)
if (start -1 >= 0) rn.push_back(mt(0, start-1, 0, d));
while (rn.size()) {
fill(segsum, segsum+n*4, 0);
fill(segct, segct+n*4, 0);
vector<ti> nrn;
int mproc = start-1;
for (ti val : rn) {
//keep them sorted from left to right
int mc = get<0>(val);
int me = get<1>(val);
int qs = get<2>(val);
int qe = get<3>(val);
int place = (qs + qe)/2;
for (int i = mproc; i > me; i--) addval(indo[i]);
for (int i = me; i >= mc; i--) {
addval(indo[i]);
int numleft = place - (start - i);
ll cur = query(numleft);
// cout << "cur: " << cur << endl;
if (cur > unol[place]) {
unol[place] = cur;
unospotl[place] = i;
}
}
mproc = mc-1;
//push back qs to place-1 and place+1 to qe
if (place-1 >= qs) nrn.push_back(mt(unospotl[place], me, qs, place-1));
if (place+1 <= qe) nrn.push_back(mt(mc, unospotl[place], place+1, qe));
}
rn.clear();
for (ti thing : nrn) rn.push_back(thing);
}
if (start -1 >= 0) rn.push_back(mt(0, start-1, 0, d));
while (rn.size()) {
fill(segsum, segsum+n*4, 0);
fill(segct, segct+n*4, 0);
vector<ti> nrn;
int mproc = start-1;
for (ti val : rn) {
//keep them sorted from left to right
int mc = get<0>(val);
int me = get<1>(val);
int qs = get<2>(val);
int qe = get<3>(val);
int place = (qs + qe)/2;
for (int i = mproc; i > me; i--) addval(indo[i]);
for (int i = me; i >= mc; i--) {
addval(indo[i]);
int numleft = place - 2*(start - i);
ll cur = query(numleft);
// cout << "cur: " << cur << endl;
if (cur > dosl[place]) {
dosl[place] = cur;
dosspotl[place] = i;
}
}
mproc = mc-1;
//push back qs to place-1 and place+1 to qe
if (place-1 >= qs) nrn.push_back(mt(dosspotl[place], me, qs, place-1));
if (place+1 <= qe) nrn.push_back(mt(mc, dosspotl[place], place+1, qe));
}
rn.clear();
for (ti thing : nrn) rn.push_back(thing);
}
ll ans = 0LL;
for (int i = 0; i <= d; i++) {
ans = max(ans, unor[i] + dosl[d-i]);
ans = max(ans, unol[i] + dosr[d-i]);
}
return ans;
}
//TL is 5 seconds, hope for the king of constant
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3576 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
15940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
15940 KB |
Output is correct |
| 2 |
Correct |
23 ms |
15940 KB |
Output is correct |
| 3 |
Correct |
26 ms |
15940 KB |
Output is correct |
| 4 |
Correct |
21 ms |
15940 KB |
Output is correct |
| 5 |
Correct |
24 ms |
15940 KB |
Output is correct |
| 6 |
Correct |
9 ms |
15940 KB |
Output is correct |
| 7 |
Correct |
8 ms |
15940 KB |
Output is correct |
| 8 |
Correct |
10 ms |
15940 KB |
Output is correct |
| 9 |
Correct |
8 ms |
15940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
834 ms |
28848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
