#include "holiday.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 100000;
std::unordered_map<int,int> code, decode;
void normalize(int n, int attraction[]){
std::vector<int> temp;
for(int i = 0; i < n; i++)
temp.push_back(attraction[i]);
std::sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
for(int i = 0; i < temp.size(); i++) {
code[temp[i]] = 1 + i;
decode[1 + i] = temp[i];
}
}
class FenwickTree{
private:
int n;
std::vector<ll> aib;
public:
FenwickTree(int n = 0){
this->n = n;
aib.resize(n + 1, 0);
}
void update(int x, int val){
if(x == 0)
return ;
while(x <= n){
aib[x] += val;
x += x ^ (x & (x - 1));
}
}
ll query(int x){
ll result = 0;
while(0 < x){
result += aib[x];
x = x & (x - 1);
}
return result;
}
///find first position with target <= query(pos)
///if it does not exist, return n + 1
int lowerthan(ll target){
int x = 0;
for(int jump = (1 << 20); 0 < jump; jump /= 2){
if(x + jump <= n && aib[x + jump] < target){
x += jump;
target -= aib[x];
}
}
return x + 1;
}
};
namespace Magicstruct{
int n;
FenwickTree app, sum;
void initialize(int n_){
n = n_;
app = FenwickTree(n);
sum = FenwickTree(n);
}
void insert(int val){
assert(0 < code[val]);
int pos = code[val];
app.update(pos, 1);
sum.update(pos, val);
//std::cout << "insert " << pos << " " << val << '\n';
}
void erase(int val){
assert(0 < code[val]);
int pos = code[val];
app.update(pos, -1);
sum.update(pos, -val);
}
///returns sum of the k biggest elements
ll query(int k){
int totalsz = app.query(n);
if(k <= 0)
return 0;
else if(totalsz <= k)
return sum.query(n);
else {
int pos = app.lowerthan(totalsz - k + 1);
//std::cout << "Query: " << pos << " " << totalsz << " " << app.query(pos - 1) << " " << k << " " << decode[pos] << '\n';
ll result = sum.query(n) - sum.query(pos - 1) - (totalsz - app.query(pos - 1) - k) * decode[pos];
return result;
}
}
}
ll v[1 + nmax], sol[1 + nmax], dp[1 + nmax];
int n, start, d;
void addinterval(int x, int y){
for(int i = x;i <= y; i++) {
Magicstruct::insert(v[i]);
}
}
void deleteinterval(int x, int y){
for(int i = x;i <= y; i++)
Magicstruct::erase(v[i]);
}
void eval(int pos, int solx, int soly){
dp[pos] = 0;
sol[pos] = solx;
for(int i = solx; i <= soly; i++){
Magicstruct::insert(v[i]);
ll result = Magicstruct::query(d - (i + start - 2 * pos));
//std::cout << "|" << pos << " " << i << " " << result << " " << d - (i + start - 2 * pos) << " " << Magicstruct::app.query(n) << '\n';
if(dp[pos] < result){
dp[pos] = result;
sol[pos] = i;
}
}
deleteinterval(solx, soly);
}
void divide(int from, int to, int solx, int soly){
if(from <= to && solx <= soly){
int mid = (from + to) / 2;
addinterval(mid, to);
eval(mid, solx, soly);
deleteinterval(mid, to);
addinterval(mid, to);
divide(from, mid - 1, solx, sol[mid]);
deleteinterval(mid, to);
addinterval(solx, sol[mid] - 1);
divide(mid + 1, to, sol[mid], soly);
deleteinterval(solx, sol[mid] - 1);
}
}
ll solve(){
Magicstruct::initialize(n);
for(int i = 0; i < n; i++)
dp[i] = sol[i] = 0;
eval(start, start, n - 1);
Magicstruct::insert(v[start]);
divide(0, start - 1, start + 1, n - 1);
Magicstruct::erase(v[start]);
ll result = 0;
for(int i = 0; i < n; i++)
result = MAX(result, dp[i]);
return result;
}
long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_;
start = start_;
d = d_;
normalize(n, attraction);
for(int i = 0; i < n; i++)
v[i] = attraction[i];
ll result1 = 0, result2 = 0;
result1 = solve();
//*
start = n - 1 - start;
for(int i = 0; i < n; i++)
if(i <= n - 1 - i)
std::swap(v[i], v[n - 1 - i]);
result2 = solve();
//*/
return MAX(result1, result2);
}
Compilation message
holiday.cpp: In function 'void normalize(int, int*)':
holiday.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
1 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
5608 KB |
Output is correct |
| 2 |
Correct |
63 ms |
5632 KB |
Output is correct |
| 3 |
Correct |
50 ms |
5572 KB |
Output is correct |
| 4 |
Correct |
50 ms |
5464 KB |
Output is correct |
| 5 |
Correct |
50 ms |
5116 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1860 KB |
Output is correct |
| 7 |
Correct |
26 ms |
3104 KB |
Output is correct |
| 8 |
Correct |
31 ms |
3616 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
760 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Correct |
4 ms |
760 KB |
Output is correct |
| 4 |
Correct |
21 ms |
760 KB |
Output is correct |
| 5 |
Correct |
19 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
376 KB |
Output is correct |
| 9 |
Correct |
6 ms |
508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
5596 KB |
Output is correct |
| 2 |
Correct |
111 ms |
13416 KB |
Output is correct |
| 3 |
Correct |
633 ms |
6276 KB |
Output is correct |
| 4 |
Correct |
19 ms |
760 KB |
Output is correct |
| 5 |
Correct |
6 ms |
376 KB |
Output is correct |
| 6 |
Correct |
7 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2070 ms |
12684 KB |
Output is correct |
| 9 |
Correct |
2036 ms |
13608 KB |
Output is correct |
