#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
long long rvid[100005];
struct segtree{
long long info[400005];
long long freq[400005];
void upd(int st,int en,int i,int pos,int val){
if(st>pos||en<pos)return;
//cerr<<"range:"<<st<<" "<<en<<"\n";
if(st==en)return info[i]+=val,freq[i]++,void();
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
freq[i]=freq[i*2]+freq[i*2+1];
}
void un_upd(int st,int en,int i,int pos,int val){
if(st>pos||en<pos)return;
if(st==en)return info[i]-=val,freq[i]--,void();
int m=(st+en)/2;
un_upd(st,m,i*2,pos,val);
un_upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
freq[i]=freq[i*2]+freq[i*2+1];
}
long long fans(int st,int en,int i,int pos){
//cerr<<"Range:"<<st<<" "<<en<<"\n";
if(st==en)return freq[i]*(rvid[st]);
if(st==en)return freq[i]*(rvid[st]);
int m=(st+en)/2;
if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos);
else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1];
}
}tr;
vector<long long>v;
int id[100005];
map<int,int>mp;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++;
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
for(int i=0;i<n;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1;
long long ans=0;
vector<int>tinf;
for(int i=0;i<n;i++){
//tinf.clear();
for(int j=i;j<n;j++){
//tinf.push_back(attraction[j]);
//sort(tinf.begin(),tinf.end(),greater<int>());
//int tsum=0;
//int x=d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start));
//int y=tinf.size();
//for(int k=0;k<min(x,y);k++)tsum+=tinf[k];
//cerr<<i<<" "<<j<<"\n";
tr.upd(1,n,1,id[j],attraction[j]);
//cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
//int temp=tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)));
//assert(tsum==temp);
if(start>=i&&start<=j&&min(abs(i-start),abs(j-start))*2+max(abs(i-start),abs(j-start))<=d)ans=max(ans,tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start))))/*,cerr<<tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)))<<"\n"*/;
//cerr<<"max:"<<ans<<"\n";
}
//cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n";
for(int j=i;j<n;j++){
tr.un_upd(1,n,1,id[j],attraction[j]);
}
}
return ans;
}
Compilation message
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
2904 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2908 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
2904 KB |
Output is correct |
7 |
Correct |
1 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5041 ms |
7256 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
638 ms |
5176 KB |
Output is correct |
2 |
Correct |
341 ms |
4956 KB |
Output is correct |
3 |
Correct |
464 ms |
5200 KB |
Output is correct |
4 |
Correct |
637 ms |
5204 KB |
Output is correct |
5 |
Correct |
492 ms |
2908 KB |
Output is correct |
6 |
Correct |
41 ms |
2908 KB |
Output is correct |
7 |
Correct |
45 ms |
4968 KB |
Output is correct |
8 |
Incorrect |
51 ms |
4988 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5051 ms |
7772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |