// ~ Be Name Khoda ~ //
#include"holiday.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e6 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 19;
const ll inf = 1e18;
vector <int> ch;
ll sum = 0, ans = 0;
int lim = 0, pt[maxn5];
int dis, st, val[maxn5];
vector <pair<int, int>> num;
struct fen{
ll fen[maxn5];
void add(int id, ll x){
////cout << "ha adding " << id << endl;
for(; id < maxn5; id += id & -id)
fen[id] += x;
}
ll get(int id){
////cout << "get " << id << endl;
ll ret = 0;
for(; id; id -= id & -id)
ret += fen[id];
return ret;
}
int find(int k){
int ret = 0;
for(int i = lg - 1; i >= 0; i--)
if(ret + (1 << i) < maxn5 && fen[ret + (1 << i)] < k){
ret += (1 << i);
k -= fen[ret];
}
return min(maxn5 - 1, ret + 1);
}
} fen1, fen2;
void add(int id){
//cout << "adding " << id << endl;
ch.pb(id);
fen1.add(pt[id], 1);
fen2.add(pt[id], val[id]);
}
void undo(int x){
while(ch.size() > x){
int id = ch.back();
ch.pop_back();
//cout << "poping " << id << endl;
fen1.add(pt[id], -1);
fen2.add(pt[id], -val[id]);
}
}
void solve(int l, int r, int optl, int optr){
//cout << "welcome " << l << ' ' << r << ' ' << optl << ' ' << optr << ' ' << ch.size() << endl;
int mid = (l + r) >> 1;
int opt = optl;
int keep = ch.size();
ll best = -1;
for(int i = mid; i < optl && i < r; i++)
add(i);
for(int i = max(mid, optl); i < optr; i++){
add(i);
int rem = dis - (min(abs(st - mid), abs(st - i)) + i - mid);
if(rem < 0)
break;
int pt;
ll sum;
if(rem == 0)
sum = 0;
else{
pt = fen1.find(rem);
sum = fen2.get(pt);
}
//cout << mid << ' ' << i << ' ' << rem << ' ' << optl << ' ' << optr << ' ' << pt << ' ' << sum << endl;
if(sum >= best){
best = sum;
opt = i;
}
}
//cout << "all here " << l << ' ' << r << endl;
ans = max(ans, best);
undo(keep);
if(r - l > 1){
for(int i = mid; i < min(r, optl); i++)
add(i);
solve(l, mid, optl, opt + 1);
undo(keep);
for(int i = max(optl, r); i < opt; i++)
add(i);
solve(mid + 1, r, opt, optr);
}
////cout << "done with " << l << ' ' << r << endl;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
if(d == 0)
return 0;
dis = d;
st = start;
//ll all = 0;
for(int i = 0; i < n; i++){
val[i] = attraction[i];
//all += val[i];
num.pb({-val[i], i});
}
////cout << all << endl;
sort(all(num));
for(int i = 0; i < n; i++)
pt[i] = lower_bound(all(num), mp(-val[i], i)) - num.begin() + 1;
solve(max(0, start - d), min(n, start + d + 1), max(0, start - d), min(n, start + d + 1));
return ans;
}
Compilation message
holiday.cpp: In function 'void undo(int)':
holiday.cpp:72:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | while(ch.size() > x){
| ~~~~~~~~~~^~~
# |
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 |
712 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
708 KB |
Output is correct |
6 |
Correct |
1 ms |
704 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
310 ms |
4996 KB |
Output is correct |
2 |
Correct |
313 ms |
5000 KB |
Output is correct |
3 |
Correct |
302 ms |
5052 KB |
Output is correct |
4 |
Correct |
302 ms |
4928 KB |
Output is correct |
5 |
Correct |
399 ms |
4708 KB |
Output is correct |
6 |
Correct |
103 ms |
1976 KB |
Output is correct |
7 |
Correct |
198 ms |
2984 KB |
Output is correct |
8 |
Correct |
263 ms |
3328 KB |
Output is correct |
9 |
Correct |
77 ms |
1696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
852 KB |
Output is correct |
2 |
Correct |
12 ms |
852 KB |
Output is correct |
3 |
Correct |
13 ms |
852 KB |
Output is correct |
4 |
Correct |
12 ms |
852 KB |
Output is correct |
5 |
Correct |
11 ms |
952 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
4 ms |
724 KB |
Output is correct |
8 |
Correct |
4 ms |
852 KB |
Output is correct |
9 |
Correct |
4 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
333 ms |
5696 KB |
Output is correct |
2 |
Correct |
341 ms |
5660 KB |
Output is correct |
3 |
Correct |
86 ms |
2592 KB |
Output is correct |
4 |
Correct |
9 ms |
852 KB |
Output is correct |
5 |
Correct |
4 ms |
840 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
4 ms |
852 KB |
Output is correct |
8 |
Correct |
486 ms |
5084 KB |
Output is correct |
9 |
Correct |
482 ms |
5156 KB |
Output is correct |