Submission #486497

#	Time	Username	Problem	Language	Result	Execution time	Memory
486497		nicolaalexandra	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	4324 ms	6216 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 (int x[]){
    lg = n / sqrt (n); /// lungime bucket

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

    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]);
    }

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

    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++;

            }

        }

    }



    /*int poz = 1, sol = 0;
    for (int i=1;i<=nr_buckets;i++){
        if (!buckets[i].size())
            continue;
        sol += dp[i][poz].first;

        int val = dp[i][poz].second;
        /// trb sa vad care e noul poz in urmatorul bucket

        /// daca sar peste mai multe bucketuri ce fac?
        while (i < nr_buckets && buckets[i+1][ buckets[i+1].size() -1].first <= val)
            i++;

        if (i + 1 > nr_buckets)
            break;

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

        }
        poz = sol_poz;
    }
*/

    return sol;
}

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

    n = _n, l = _l;
    build (v);

}

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();

    poz++;

    int idx = what_bucket[poz];

    sterge (idx,poz);

    //buckets[idx].erase(make_pair(v[poz].first,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);
    //buckets[sol].insert(v[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:77:26: warning: unused variable 'poz' [-Wunused-variable]
   77 |     int i = 1, val = -1, poz, sol = 0;
      |                          ^~~
elephants.cpp: In function 'void sterge(int, int)':
elephants.cpp:162: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]
  162 |     for (i=0;i<buckets[idx].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:166: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]
  166 |     for (int j=i+1;j<buckets[idx].size();j++)
      |                    ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void adauga(int, int)':
elephants.cpp:174: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]
  174 |     for (i=0;i<buckets[idx].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~

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