Submission #486493

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

elephants

#include <bits/stdc++.h>
#include "elephants.h"
#define DIM 150010
#define DIMBUCKET 400
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 poz = 1, sol = 0;
    for (int i=1;i<=nr_buckets;i++){
        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;
    for (int i=0;i<n;i++)
        cin>>x[i];

    init(n,l,x);

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


    return 0;
}
*/

Compilation message (stderr)

elephants.cpp: In function 'void sterge(int, int)':
elephants.cpp:114: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]
  114 |     for (i=0;i<buckets[idx].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:118: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]
  118 |     for (int j=i+1;j<buckets[idx].size();j++)
      |                    ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void adauga(int, int)':
elephants.cpp:126: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]
  126 |     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