#include "holiday.h"
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 5, INF = 2e9;
int n, d, start, a[N], ori[N], sz; long long ans = -INF;
vector<int> val;
struct node{
int cnt; long long sum;
node *l, *r;
node(){
l = r = nullptr, cnt = sum = 0;
}
};
node *root[N];
node *build(int l, int r){
node *p = new node();
if(l == r){
return p;
}
int mid = (l + r) / 2;
p -> l = build(l, mid);
p -> r = build(mid + 1, r);
return p;
}
node* upd(node *k, int tl, int tr, int i, int x){
node *p = new node();
if(tl == tr){
p -> cnt = k -> cnt + 1;
p -> sum = k -> sum + ori[tl];
return p;
}
int mid = (tl + tr) / 2;
if(i <= mid){
p -> l = upd(k -> l, tl, mid, i, x);
p -> r = k -> r;
} else{
p -> l = k -> l;
p -> r = upd(k -> r, mid + 1, tr, i, x);
}
p -> cnt = p -> l -> cnt + p -> r -> cnt;
p -> sum = p -> l -> sum + p -> r -> sum;
return p;
}
long long query(node *l, node *r, int tl, int tr, int k){
if(tl == tr){
return 1LL * ori[tl] * min(k, r -> cnt - l -> cnt);
}
int mid = (tl + tr) / 2;
if(r -> r -> cnt - l -> r -> cnt >= k){
return query(l -> r, r -> r, mid + 1, tr, k);
} else{
// cout << ori[mid + 1] << " " << r -> r -> cnt - l -> r -> cnt << " " << r -> r -> sum - l -> r -> sum << endl;
return r -> r -> sum - l -> r -> sum + query(l -> l, r -> l, tl, mid, k - (r -> r -> cnt - l -> r -> cnt));
}
}
long long cost(int l, int start, int r){
int queryop = min(d - (r - l + min(r - start, start - l)), r - l + 1);
if(queryop < 0) return -INF;
// cout << l << ' ' << start << " " << r << ' ' << queryop << " " << query(root[l - 1], root[r], 0, sz, queryop)<< endl;
return query(root[l - 1], root[r], 0, sz, queryop);
}
void dnc(int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l + r) / 2;
pair<long long, int> best = {-INF, 0};
for(int i = optl; i <= min(optr, mid); i++){
best = max(best, {cost(i, start, mid), i});
}
ans = max(ans, best.first);
dnc(l, mid - 1, optl, best.second);
dnc(mid + 1, r, best.second, optr);
}
int findMaxAttraction(int n, int start, int d, int a[]){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> start >> d;
start++;
for(int i = 1; i <= n; i++) cin >> a[i], val.push_back(a[i]);
sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
for(int i = 0; i < (int) val.size(); i++) ori[i] = val[i];
sz = val.size() - 1;
root[0] = build(0, sz);
for(int i = 1; i <= n; i++){
a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
root[i] = upd(root[i - 1], 0, sz, a[i], 1);
}
dnc(start, n, 1, start);
return ans;
}
Compilation message
holiday.cpp:9:1: error: 'vector' does not name a type
9 | vector<int> val;
| ^~~~~~
holiday.cpp: In function 'long long int query(node*, node*, long long int, long long int, long long int)':
holiday.cpp:55:32: error: 'min' was not declared in this scope
55 | return 1LL * ori[tl] * min(k, r -> cnt - l -> cnt);
| ^~~
holiday.cpp: In function 'long long int cost(long long int, long long int, long long int)':
holiday.cpp:68:36: error: 'min' was not declared in this scope
68 | int queryop = min(d - (r - l + min(r - start, start - l)), r - l + 1);
| ^~~
holiday.cpp:68:19: error: 'min' was not declared in this scope
68 | int queryop = min(d - (r - l + min(r - start, start - l)), r - l + 1);
| ^~~
holiday.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
holiday.cpp:76:5: error: 'pair' was not declared in this scope
76 | pair<long long, int> best = {-INF, 0};
| ^~~~
holiday.cpp:2:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
1 | #include "holiday.h"
+++ |+#include <utility>
2 | #define int long long
holiday.cpp:76:10: error: expected primary-expression before 'long'
76 | pair<long long, int> best = {-INF, 0};
| ^~~~
holiday.cpp:77:28: error: 'min' was not declared in this scope; did you mean 'mid'?
77 | for(int i = optl; i <= min(optr, mid); i++){
| ^~~
| mid
holiday.cpp:78:9: error: 'best' was not declared in this scope
78 | best = max(best, {cost(i, start, mid), i});
| ^~~~
holiday.cpp:78:16: error: 'max' was not declared in this scope
78 | best = max(best, {cost(i, start, mid), i});
| ^~~
holiday.cpp:80:20: error: 'best' was not declared in this scope
80 | ans = max(ans, best.first);
| ^~~~
holiday.cpp:80:11: error: 'max' was not declared in this scope
80 | ans = max(ans, best.first);
| ^~~
holiday.cpp: In function 'long long int findMaxAttraction(long long int, long long int, long long int, long long int*)':
holiday.cpp:86:5: error: 'ios_base' has not been declared
86 | ios_base::sync_with_stdio(0); cin.tie(0);
| ^~~~~~~~
holiday.cpp:86:35: error: 'cin' was not declared in this scope
86 | ios_base::sync_with_stdio(0); cin.tie(0);
| ^~~
holiday.cpp:2:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
1 | #include "holiday.h"
+++ |+#include <iostream>
2 | #define int long long
holiday.cpp:89:46: error: 'val' was not declared in this scope
89 | for(int i = 1; i <= n; i++) cin >> a[i], val.push_back(a[i]);
| ^~~
holiday.cpp:90:10: error: 'val' was not declared in this scope
90 | sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
| ^~~
holiday.cpp:90:5: error: 'sort' was not declared in this scope; did you mean 'short'?
90 | sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
| ^~~~
| short
holiday.cpp:90:46: error: 'unique' was not declared in this scope
90 | sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
| ^~~~~~
holiday.cpp:95:16: error: 'lower_bound' was not declared in this scope
95 | a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
| ^~~~~~~~~~~
