Submission #1003231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003231		vjudge1	Rice Hub (IOI11_ricehub)	C++17	0 / 100	14 ms	2652 KiB

ricehub

#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 (stderr)

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

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