Submission #1003363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003363		0pt1mus23	Rice Hub (IOI11_ricehub)	C++14	0 / 100	68 ms	12028 KiB

ricehub

/*
    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()
        // 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());
            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());
            }
            else{
                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()){
            auto node = *right.begin();
            node = *right.rbegin();
            auto rnode = *right.rbegin();
                
            if(currsum + min(abs(node.first - arr[i]),abs(rnode.first -arr[i]))>B){
                break;
            }
            // cout<<currsum<<" --v-- "<<node.second<<endl;
            if(currsum + abs(node.first - arr[i])<currsum+abs(rnode.first - arr[i])){
                
            // 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());
            }
            else{
                if(currsum + abs(rnode.first  -arr[i])>B){
                    break;
                }
                currsum+=abs(arr[i]- rnode.first);
                upd(comp[rnode.first],rnode.first,1);
                goturdum.insert({rnode.second,rnode.first});
                right.erase(--right.end());
                
            }
        }
        // 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 (stderr)

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;
      |         ^~~

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