Submission #1003709

#TimeUsernameProblemLanguageResultExecution timeMemory
10037090pt1mus23Rice Hub (IOI11_ricehub)C++14
0 / 100
4 ms604 KiB
/* 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=1; /* her i ucun ele j tapaqki : j<i j ni goturmesek i+1 right terefden nese ekstra goture bilirik */ int l =2; int r = n; vector<int> pref(n,0); for(int i=1;i<n;i++){ arr[i]-=arr[0]; } arr[0]=0; for(int i=0;i<n;i++){ pref[i]+=arr[i]; if(i){ pref[i]+=pref[i-1]; } } auto calc = [&](int lx,int rx,int orta){ return (pref[rx] - (orta?pref[orta -1]:0)) - arr[orta] * (rx - orta +1)+ arr[orta] * (orta- lx) - (pref[orta-1] - (lx?pref[lx -1]:0)); }; while(l<=r){ int mid = (l+r)/2; bool check=false; int x = mid%2 ; for(int i =0;i<n-mid+1;i++){ int c =0; int lx = i; int rx = i+mid-1; int orta = i+x; if(mid%2){ c+= (pref[rx] - (orta?pref[orta -1]:0)) - arr[orta] * (rx - orta +1); c+= arr[orta] * (orta- lx) - (pref[orta-1] - (lx?pref[lx -1]:0)); // cout<<i<<" "<<mid<<" "<<c<<endl; } else{ vector<int> xxx; // if(orta!=lx){ xxx.pb(calc(lx,rx,orta)); // } if(orta!=lx){ xxx.pb(calc(lx,rx,orta-1)); } if(orta!=rx){ xxx.pb(calc(lx,rx,orta+1)); } sort(all(xxx)); c = xxx[0]; } if(c<=B){ check=true; break; } } if(check){ ans=mid; l=mid+1; } else{ r=mid-1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...