/*
neynedigimi bilmirem
*/
#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;
}
set<pair<int,int>> right;
set<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]]-1);
int y = qry(sze).first - res.first;
currsum = res.second * arr[i] - res.first;
currsum += y - arr[i]*(goturdum.size() - res.second);
// goturdum.insert()
if(right.count({arr[i],i}) && !goturdum.count({arr[i],i})){
right.erase({arr[i],i});
goturdum.ins({arr[i],i});
}
// cout<<i<<" sum:"<<currsum<<endl;
// cout<<i<<" "<<currsum<<" boyuklerinsumu: "<<y<<" balacacount:"<<res.second<<" balacasum:"<<res.first<<endl;
while(currsum>B && !goturdum.empty()){
auto left = *(goturdum.begin());
int lc = abs(arr[i] - left.second);
currsum-=lc;
upd(comp[left.second] , -left.second,-1 );
goturdum.erase(goturdum.begin());
}
// cout<<i<<" newsum: "<<goturdum.size()<<endl;
// teze elementler gotur
while(!right.empty()){
auto node = *right.begin();
// cout<<currsum<<" --v-- "<<node.second<<endl;
if(currsum + abs(node.first - arr[i])>B){
break;
}
// cout<<i<<" : aldiq"<<node.second<<endl;
currsum+=abs(arr[i]- node.first);
upd(comp[node.first],node.first,1);
goturdum.insert({node.second,node.first});
right.erase(right.begin());
}
// cout<<i<<" :\n";
// cout<<"sum: "<<currsum<<endl;
// for(auto v:goturdum){
// cout<<v.first<<" "<<v.second<<endl;
// }
// cout<<"-------------"<<endl;
ans=max(ans,(int)goturdum.size());
}
return ans;
}
Compilation message
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:49:9: warning: unused variable 'cnt' [-Wunused-variable]
49 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2592 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2612 KB |
Output is correct |
| 3 |
Correct |
81 ms |
11600 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
11624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
