Submission #550087

#	Time	Username	Problem	Language	Result	Execution time	Memory
550087		neki	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	425 ms	5120 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();
}

int cnt=0;
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){
    	es[ind].odsek=nov;
    	
        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(), [](e* a, e* b){return (*a)<(*b);});
    calcdp(dp[nov]);
    
    ++cnt;if(cnt%mm==0) build();
    
    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 'int update(int, int)':
elephants.cpp:57:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     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;}
      |                                      ~^~~~~~~~~~

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