#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
const ll MOD = 998244353;
struct NODE{
int cnt, l, r;
ll sum;
};
int N, start, D, days;
vector<ll> arr;
vector<ll> A;
int nodeN;
NODE seg1[2000010];
int seg2[1200010];
int roots[100010];
ll decomp[100010];
void init2(int x, int s, int e){
if(s==e){
seg2[x] = 1;
}
else{
seg2[x] = 0;
int m = (s+e)/2;
init2(x*2, s, m);
init2(x*2+1, m+1, e);
}
}
void propagate2(int x){
if(seg2[x]){
seg2[x*2] = seg2[x];
seg2[x*2+1] = seg2[x];
seg2[x] = 0;
}
}
int query2(int x, int s, int e, int f){
if(s==e){
return seg2[x];
}
propagate2(x);
int m = (s+e)/2;
if(f<=m){
return query2(x*2, s, m, f);
}
else{
return query2(x*2+1, m+1, e, f);
}
}
void update2(int x, int s, int e, int fs, int fe, int v){
if(fe<s||e<fs){
return;
}
if(fs<=s&&e<=fe){
seg2[x] = v;
return;
}
propagate2(x);
int m = (s+e)/2;
update2(x*2, s, m, fs, fe, v);
update2(x*2+1, m+1, e, fs, fe, v);
}
void init1(int x, int s, int e){
seg1[x].cnt = seg1[x].sum = 0;
nodeN = max(nodeN, x);
if(s!=e){
seg1[x].l = x*2;
seg1[x].r = x*2+1;
int m = (s+e)/2;
init1(x*2, s, m);
init1(x*2+1, m+1, e);
}
}
ll query1(int x, int s, int e, int a, int b){
//printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
if(a==1&&b==seg1[x].cnt){
return seg1[x].sum;
}
if(s==e){
printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
printf("hello\n");
}
int m = (s+e)/2;
ll result = 0;
if(seg1[seg1[x].l].cnt >= a){
result += query1(seg1[x].l, s, m, a, min(b, seg1[seg1[x].l].cnt));
}
if(seg1[seg1[x].l].cnt < b){
result += query1(seg1[x].r, m+1, e, max(1, a-seg1[seg1[x].l].cnt), b-seg1[seg1[x].l].cnt);
}
return result;
}
void update1(int x, int s, int e, int f, ll v){
//printf("--------- %d %d %d %d %lld\n", x, s, e, f, v);
seg1[x].cnt++;
seg1[x].sum += v;
if(s!=e){
int m = (s+e)/2;
if(f<=m){
seg1[++nodeN] = seg1[seg1[x].l];
seg1[x].l = nodeN;
update1(nodeN, s, m, f, v);
}
else{
seg1[++nodeN] = seg1[seg1[x].r];
seg1[x].r = nodeN;
update1(nodeN, m+1, e, f, v);
}
}
}
vector<ll> oneWay(){
int M = A.size()-1;
if(M==0){
vector<ll> result(D+1);
return result;
}
nodeN = 0;
init1(1, 1, N);
init2(1, 1, D);
roots[0] = 1;
for(int i=1; i<=M; i++){
roots[i] = ++nodeN;
seg1[roots[i]] = seg1[roots[i-1]];
update1(roots[i], 1, N, A[i], decomp[A[i]]);
}
for(int i=2; i<=M; i++){
int left = i, right = D, mid = (left+right)/2;
while(left<right){
int t = query2(1, 1, D, mid);
if((2*i-1<=mid || query1(roots[t], 1, N, max(2*t-mid, 1), 2*t-mid+1) < decomp[A[i]])){
right = mid;
}
else{
left = mid+1;
}
mid = (left+right)/2;
}
update2(1, 1, D, mid, D, i);
}
vector<ll> result;
result.push_back(0);
for(int i=1; i<=D; i++){
int t = query2(1, 1, D, i);
result.push_back(query1(roots[t], 1, N, max(2*t-i, 1), t));
}
return result;
}
vector<ll> roundTrip(){
int M = A.size()-1;
if(M==0){
vector<ll> result(D+1);
return result;
}
nodeN = 0;
init1(1, 1, N);
init2(1, 1, D);
roots[0] = 1;
for(int i=1; i<=M; i++){
roots[i] = ++nodeN;
seg1[roots[i]] = seg1[roots[i-1]];
update1(roots[i], 1, N, A[i], decomp[A[i]]);
}
for(int i=2; i<=M; i++){
int left = 2*i-1, right = D, mid = (left+right)/2;
while(left<right){
int t = query2(1, 1, D, mid);
if((3*i-2<=mid || query1(roots[t], 1, N, max(3*t-mid-1, 1), 3*t-mid+1) < decomp[A[i]])){
right = mid;
}
else{
left = mid+1;
}
mid = (left+right)/2;
}
update2(1, 1, D, mid, D, i);
}
vector<ll> result;
result.push_back(0);
result.push_back(0);
result.push_back(0);
for(int i=1; i<=D; i++){
int t = query2(1, 1, D, i);
result.push_back(query1(roots[t], 1, N, max(3*t-i-1, 1), t));
}
return result;
}
vector<pair<ll, int> > temp;
ll findMaxAttraction(int input1, int input2, int input3, int input4[]){
N = input1;
start = input2;
days = input3;
for(int i=0; i<N; i++){
arr.push_back(input4[i]);
temp.push_back({input4[i], i});
}
D = 3*N;
sort(all(temp));
for(int i=0; i<N; i++){
arr[temp[i].second] = i+1;
decomp[i+1] = temp[i].first;
}
vector<ll> r1, r2, r3, r4;
A.push_back(0);
for(int i=start; i>=0; i--){
A.push_back(arr[i]);
}
r1 = oneWay();
A.clear();
A.push_back(0);
for(int i=start-1; i>=0; i--){
A.push_back(arr[i]);
}
r2 = roundTrip();
A.clear();
A.push_back(0);
for(int i=start+1; i<N; i++){
A.push_back(arr[i]);
}
r3 = roundTrip();
A.clear();
A.push_back(0);
for(int i=start; i<N; i++){
A.push_back(arr[i]);
}
r4 = oneWay();
ll result = 0;
for(int i=0; i<=days; i++){
result = max(result, r1[i]+r3[days-i]);
result = max(result, r2[i]+r4[days-i]);
}
return result;
}
| # |
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 |
696 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 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 |
Runtime error |
136 ms |
65536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2508 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2516 KB |
Output is correct |
| 4 |
Correct |
16 ms |
2224 KB |
Output is correct |
| 5 |
Correct |
14 ms |
2004 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
1236 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
65536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
