#include "ricehub.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T> using ot = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int sze=1e5 +10;
pair<int,int> T[sze+10];
const int inf = INT_MAX;
void upd(int node,int v,int y){
node++;
while(node<=sze){
T[node].first+=v;
T[node].second+=y;
node += (node & -node);
}
}
pair<int,int> qry(int node){
node++;
pair<int,int> res;
while(node>0){
res.first+=T[node].first;
res.second += T[node].second;
node -= (node & -node);
}
return res;
}
int besthub(int n, int mxL, int arr[], long long B){
int ans=0;
/*
her i ucun ele j tapaqki :
j<i
j ni goturmesek i+1 right terefden nese ekstra goture bilirik
*/
int cnt=0;
for(int i =1;i<n;i++){
arr[i]-=arr[0];
}
arr[0]=0;
map<int,int> comp;
int xx=0;
for(int i=0;i<n;i++){
comp[arr[i]]++;
}
for(auto& v:comp){
v.second = ++xx;
}
ot<pair<int,int>> right;
ot<pair<int,int>> goturdum;
for(int i=0;i<n;i++){
right.ins({arr[i],i});
}
int currsum=0;
while(!right.empty()){
auto node = (*right.begin());
if(currsum+ node.first>B){
break;
}
currsum+=node.first;
upd(comp[node.first],node.first,1);
goturdum.insert({node.second,node.first});
right.erase(right.begin());
}
ans=goturdum.size();
// cout<<0<<" "<<currsum<<endl;
for(int i=1;i<n;i++){
pii res = qry(comp[arr[i]]);
int y = currsum - res.first;
currsum = res.second * arr[i] - res.first;
currsum += y - arr[i]*(goturdum.size() - res.second);
// cout<<i<<" "<<currsum<<" boyuklerinsumu: "<<y<<" balacacount:"<<res.second<<" balacasum:"<<res.first<<endl;
while(currsum>B && !goturdum.empty()){
auto left = *(goturdum.begin());
auto right = *(goturdum.rbegin());
int lc = abs(arr[i] - left.second);
int rc = abs(arr[i] - right.second);
if(lc>rc){
currsum-=lc;
upd(comp[left.second] , -left.second,-1 );
goturdum.erase(goturdum.begin());
}
currsum-=rc;
upd(comp[right.second] , -right.second,-1 );
goturdum.erase(--goturdum.end());
}
// cout<<i<<" newsum: "<<goturdum.size()<<endl;
// teze elementler gotur
while(!right.empty() && true){
auto it = right.lower_bound({arr[i],-1});
auto it2 = it;
int es = inf;
int cs = inf;
if(it2!=right.begin()){
it2--;
}
if(it!=right.end()){
cs = abs( (*it).first - arr[i]);
}
if(it2!=it){
es = abs( (*it2).first - arr[i]);
}
if(currsum + min(es,cs)>B){
break;
}
if(cs==es){
if((*it).second>(*it2).second){
currsum+=cs;
auto nd = *it;
upd(comp[nd.first],nd.first,1);
goturdum.ins({nd.second,nd.first});
right.erase(it);
}
else{
currsum+=es;
auto nd = *it2;
upd(comp[nd.first],nd.first,1);
goturdum.ins({nd.second,nd.first});
right.erase(it2);
}
}
else{
if(cs>es){
currsum+=cs;
auto nd = *it;
upd(comp[nd.first],nd.first,1);
goturdum.ins({nd.second,nd.first});
right.erase(it);
}
else{
currsum+=es;
auto nd = *it2;
upd(comp[nd.first],nd.first,1);
goturdum.ins({nd.second,nd.first});
right.erase(it2);
}
}
}
ans=max(ans,(int)goturdum.size());
}
return ans;
}
Compilation message
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:46:9: warning: unused variable 'cnt' [-Wunused-variable]
46 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
