Submission #1082170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082170		CELD_07	Rice Hub (IOI11_ricehub)	C++17	100 / 100	324 ms	8796 KiB

ricehub

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl "\n"
#define inf LLONG_MAX
#define vll vector<ll>
#define sd second
#define ft first
#define al(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
vector<ll> v1;
vector<pair<ll, ll>> t;
inline void build(ll v, ll tl, ll tr){
if(tl==tr){
t[v]={v1[tl], -v1[tl]};
}else{
ll tm=(tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v].ft=t[v*2].ft+t[v*2+1].ft;
t[v].sd=t[v*2].sd+t[v*2+1].sd;
}
}
inline ll query(ll v, ll tl, ll tr, ll l, ll r){
if(tl>r || tr<l)return 0;
if(tl>=l && tr<=r)return t[v].ft;
ll tm=(tl+tr)/2;
return query(v*2, tl, tm, l, r)+query(v*2+1, tm+1, tr, l, r);
}
inline ll query1(ll v, ll tl, ll tr, ll l, ll r){
if(tl>r || tr<l)return 0;
if(tl>=l && tr<=r)return t[v].sd;
ll tm=(tl+tr)/2;
return query1(v*2, tl, tm, l, r)+query1(v*2+1, tm+1, tr, l, r);
}
int besthub(int R, int L, int X[], long long B){
    ll a, b, c, d, e, f;
    a=R;
    b=L;
    c=B;
    t.clear();
    v1.clear();
    t.resize(4*a);
    v1.resize(a);
    for(int i=0; i<a; i++)v1[i]=X[i];
    build(1, 0, a-1);
    ll res=0;
    for(int i=0; i<a; i++){
    ll tl=i, tr=a-1;
    while(tl<=tr){
    ll tm2=(tl+tr)/2, tm=(i+tm2)/2, tm1=tm+1;
    ll// o=query1(1, 0, a-1, i, tm)+(v1[tm]*((tm-i)+1)), o1=query(1, 0, a-1, tm, tm2)-(v1[tm]*((tm2-tm)+1));
    o2=query1(1, 0, a-1, i, tm1)+(v1[tm1]*((tm1-i)+1)), o3=query(1, 0, a-1, tm1, tm2)-(v1[tm1]*((tm2-tm1)+1));
    //cout<<i<<" "<<tl<<" "<<tr<<endl;
    //if(i==2)cout<<o<<" "<<o1<<" "<<tm2<<" "<<tm1<<" "<<tm<<endl;
    //if(o+o1<=c)res=max(res, (tm2-i)+1);
    if(o2+o3<=c)res=max(res, (tm2-i)+1);
    if(o2+o3<=c)tl=tm2+1;
    else tr=tm2-1;
    }
    }
    return res;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:42:11: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   42 |     ll a, b, c, d, e, f;
      |           ^
ricehub.cpp:42:17: warning: unused variable 'd' [-Wunused-variable]
   42 |     ll a, b, c, d, e, f;
      |                 ^
ricehub.cpp:42:20: warning: unused variable 'e' [-Wunused-variable]
   42 |     ll a, b, c, d, e, f;
      |                    ^
ricehub.cpp:42:23: warning: unused variable 'f' [-Wunused-variable]
   42 |     ll a, b, c, d, e, f;
      |                       ^

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32