Submission #549891

#	Time	Username	Problem	Language	Result	Execution time	Memory
549891		neki	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	340 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;
    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;nods.ps(vsi[i]);}
        calcdp(nods);
        dp.ps(nods);
    }
}

void init(int N, int L, int* X){
    n=N, l=L;
    
    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();
}

int update(int ind, int y){
    int nov; for(int i=0;i<dp.size();++i) if(y<(*(dp[i].back())).pos){nov=i;break;}
    int star = es[ind].odsek;
    
    if(nov!=star){
        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]);
    }
    sort(dp[nov].begin(), dp[nov].end());
    calcdp(dp[nov]);
    
    int curpos=-1, ret=0;
    for(auto&& v: dp) if(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 'int update(int, int)':
elephants.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     int nov; for(int i=0;i<dp.size();++i) if(y<(*(dp[i].back())).pos){nov=i;break;}
      |                          ~^~~~~~~~~~
elephants.cpp:63:15: warning: 'nov' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |         dp[nov].ps(&es[ind]);
      |               ^

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