Submission #550080

#	Time	Username	Problem	Language	Result	Execution time	Memory
550080		neki	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9018 ms	2600 KiB

elephants

#include <bits/stdc++.h>

using namespace std;

#define vc vector
#define ps push_back

const int mm=350;
int n, l;

struct e{
    int i, pos, val, odsek, kok;
    
    e(int i_, int pos_): i(i_), pos(pos_){}
    
    bool operator<(const e& oth){return pos < oth.pos;}
};
vc<e> es;

vc<vc<e*>> dp;

void calcdp(vc<e*>& arr){
    int siz=arr.size(), nas=siz;
    if(siz==0) return;
    for(int i=siz-1;i>=0;--i){
        while((*arr[i]).pos+l<= (*arr[nas-1]).pos) --nas;
        if(nas<siz) (*arr[i]).val=(*arr[nas]).val, (*arr[i]).kok=(*arr[nas]).kok + 1;
        else (*arr[i]).val=(*arr[i]).pos+l, (*arr[i]).kok=1;
    }
}

void build(){
    vc<e*> vsi;
    for(auto v : dp) for(auto u : v ) vsi.push_back(u);
    
    dp.clear();
    for(int ods=0;ods<n;ods+=mm){
        vc<e*> nods;
        for(int i=ods;i<min(n, ods+mm);++i){(*vsi[i]).odsek=ods/mm;nods.ps(vsi[i]);}
        calcdp(nods);
        dp.ps(nods);
    }
}

void init(int N, int L, int* X){
    n=N, l=L+1;
    
    for(int i=0;i<n;++i) es.ps(e(i, X[i]));
    dp.ps({});
    for(int i=0;i<n;++i)dp[0].ps(&es[i]);
    build();
}

void printdp(){
    for(auto&& u:dp){
        for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
    }
}

int update(int ind, int y){
    es[ind].pos=y;
    int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<(*(dp[i].back())).pos){nov=i;break;}
    int star = es[ind].odsek;
    if(nov!=star){
    	assert(star<dp.size());
        vc<e*> shrani=dp[star];
        dp[star].clear();
        for(auto v : shrani) if((*v).i != ind) dp[star].ps(v);
        calcdp(dp[star]);
        
        dp[nov].ps(&es[ind]);
    }
    //printdp();
    sort(dp[nov].begin(), dp[nov].end(), [](e* a, e* b){
        return (*a)<(*b);
    });
    calcdp(dp[nov]);
    
    //printdp();
    
    int curpos=-1, ret=0;
    for(auto&& v: dp) if(v.size()>0 and curpos<=(*(v.back())).pos){
        int L=0, R=v.size()-1; //nani
        while(L<R){
            int mid=(L+R)/2;
            if(curpos <= (*v[mid]).pos) R=mid;
            else L=mid+1;
        }
        
        curpos= (*v[L]).val;
        ret+= (*v[L]).kok;
    }
    
    return ret;
}

Compilation message (stderr)

elephants.cpp: In function 'void printdp()':
elephants.cpp:56:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |         ^~~
elephants.cpp:56:82: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |         for(auto&& v : u) cout << (*v).pos<<" "<<(*v).val<<" "<<(*v).kok<<" | "; cout << endl;
      |                                                                                  ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:62:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<(*(dp[i].back())).pos){nov=i;break;}
      |                                      ~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from elephants.cpp:1:
elephants.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      assert(star<dp.size());
      |             ~~~~^~~~~~~~~~

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