Submission #486504

#	Time	Username	Problem	Language	Result	Execution time	Memory
486504		nicolaalexandra	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	0 ms	332 KiB

elephants

#include <bits/stdc++.h>
#define DIM 150010
#define DIMBUCKET 400
#include "elephants.h"
using namespace std;

int n,lg,nr_buckets,l,q,cnt,poz,val;
int what_bucket[DIM],x[DIM];
pair <int,int> v[DIM],aux[DIM],dp[DIMBUCKET][DIMBUCKET*2];
vector <pair<int,int> > buckets[DIMBUCKET];

void update_bucket (int bucket){

    int el = 0;
    for (auto it : buckets[bucket])
        aux[++el] = it;

    int j = el+1;
    for (int i=el;i;i--){

        while (aux[j-1].first > aux[i].first + l)
            j--;

        if (j <= el){
            dp[bucket][i].first = dp[bucket][j].first + 1;
            dp[bucket][i].second = dp[bucket][j].second;
        } else {
            dp[bucket][i].first = 1;
            dp[bucket][i].second = aux[i].first + l;
        }
    }

}


void build (){

    for (int i=1;i<=nr_buckets;i++)
        buckets[i].clear();
    sort (v+1,v+n+1);

    for (int i=1;i<=n;i++){
        what_bucket[v[i].second] = i / lg;
        if (i % lg)
            what_bucket[v[i].second]++;

        buckets[what_bucket[v[i].second]].push_back(v[i]);
    }

    for (int i=1;i<=nr_buckets;i++)
        sort (buckets[i].begin(),buckets[i].end());

    /// dp[bucket][i] - nr min de intervale cu care pot sa acopar toate punctele
    /// din bucketul asta, incepand de la al i - lea, si care e cea mai din dreapta poz
    /// pt care pot sa fac asta

    for (int i=1;i<=nr_buckets;i++){

        update_bucket(i);

    }


}

int query (){


    int i = 1, val = -1, poz, sol = 0;
    while (i <= nr_buckets){

        if (buckets[i].empty()){
            i++;
            continue;
        }

        if (val == -1){
            sol += dp[i][1].first;
            val = dp[i][1].second;

            i++;
        } else {

            if (buckets[i][ buckets[i].size()-1 ].first <= val)
                i++;

            else {

                /// caut binar pe primul > val

                int st = 1, dr = buckets[i].size(), sol_poz = 1;
                while (st <= dr){
                    int mid = (st+dr)>>1;
                    if (buckets[i][mid-1].first > val){
                        sol_poz = mid;
                        dr = mid-1;
                    } else st = mid+1;
                }

                sol += dp[i][sol_poz].first;
                val = dp[i][sol_poz].second;

                i++;

            }

        }

    }




    return sol;
}

void init (int _n, int _l, int x[]){

    n = _n, l = _l;

    lg = n / sqrt (n); /// lungime bucket

    nr_buckets = n / lg;
    if (n % lg)
        nr_buckets++;

    for (int i=1;i<=n;i++){
        v[i].first = x[i-1];
        v[i].second = i;
    }

    build ();

}

void sterge (int idx, int poz){
    int i;
    for (i=0;i<buckets[idx].size();i++)
        if (buckets[idx][i] == v[poz])
            break;

    for (int j=i+1;j<buckets[idx].size();j++)
        buckets[idx][j-1] = buckets[idx][j];

    buckets[idx].pop_back();
}

void adauga (int idx, int poz){
    int i;
    for (i=0;i<buckets[idx].size();i++)
        if (v[poz].first <= buckets[idx][i].first)
            break;
    buckets[idx].push_back(make_pair(0,0));
    for (int j=buckets[idx].size()-1;j>i;j--)
        buckets[idx][j] = buckets[idx][j-1];
    buckets[idx][i] = v[poz];
}

int update (int poz, int val){
    cnt++;
    if (cnt == lg){ /// refac bucketurile

        build();
        cnt = 0;
    }

    poz++;

    int idx = what_bucket[poz];

    sterge (idx,poz);


    update_bucket (idx);

    /// trb sa vad in ce bucket l as pune
    v[poz].first = val;

    int st = 1, dr = nr_buckets, sol = 1;
    while (st <= dr){
        int mid = (st+dr)>>1;

        if (buckets[mid][0].first <= val){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;

    }

    what_bucket[poz] = sol;


    adauga(sol,poz);

    update_bucket(sol);


    return query();
}
/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    cin>>n>>l>>q;
    for (int i=0;i<n;i++)
        cin>>x[i];

    init(n,l,x);

    //cin>>q;
    for (;q--;){
        int useless;
        cin>>poz>>val>>useless;
        cout<<update (poz,val)<<"\n";
    }


    return 0;
}
*/

Compilation message (stderr)

elephants.cpp: In function 'int query()':
elephants.cpp:69:26: warning: unused variable 'poz' [-Wunused-variable]
   69 |     int i = 1, val = -1, poz, sol = 0;
      |                          ^~~
elephants.cpp: In function 'void sterge(int, int)':
elephants.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (i=0;i<buckets[idx].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int j=i+1;j<buckets[idx].size();j++)
      |                    ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void adauga(int, int)':
elephants.cpp:150:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (i=0;i<buckets[idx].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3