Submission #506086

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

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sq = 391;
int qsize = 0, len;
vector<int> arr,rev,part[sq];
vector<pair<int,int> > dp[sq];
void cntdp(int sidx){
    dp[sidx].resize(part[sidx].size(),make_pair(0,0));
    for(int j=part[sidx].size();j>0;j--){
        auto it = upper_bound(part[sidx].begin(),part[sidx].end(),part[sidx][j-1]+len);
        if(it == part[sidx].end()) dp[sidx][j-1] = make_pair(1,part[sidx][j-1]+len);
        else{
            int idx = it-part[sidx].begin();
            dp[sidx][j-1] = make_pair(1+dp[sidx][idx].first,dp[sidx][idx].second);
        }
    }
    
}
void recalc(){
    for(int i=0;i<sq;i++){
        for(int it : part[i]) arr.emplace_back(it);
        part[i].clear();
    }
    for(int i=0;i<arr.size();i++){
        part[i/sq].push_back(arr[i]);
    }
    for(int i=0;i<sq;i++) cntdp(i);
    arr.clear();
}
int upd(int idx,int nxt){
    for(int i=0;i<sq;i++){
        if(part[i].empty() || nxt <= part[i].back()){
            part[i].insert(lower_bound(part[i].begin(),part[i].end(),nxt),nxt);
            cntdp(i);
            break;
        }
    }
    int curr = rev[idx];
    for(int i=0;i<sq;i++){
        if(!part[i].empty() && part[i][0] <= curr && curr <= part[i].back()){
            part[i].erase(lower_bound(part[i].begin(),part[i].end(),curr));
            cntdp(i);
            break;
        }
    }
    rev[idx] = nxt;
    int res = 0,start = -1;
    for(int i=0;i<sq;i++){
        if(upper_bound(part[i].begin(),part[i].end(),start) == part[i].end()) continue;
        int idx = upper_bound(part[i].begin(),part[i].end(),start) - part[i].begin();
        res += dp[i][idx].first;
        start = dp[i][idx].second;
    }
    return res;
}

void init(int N, int L, int X[]){
    len = L;
    for(int i=0;i<N;i++) arr.emplace_back(X[i]);
    rev.resize(N,0);
    for(int i=0;i<N;i++) rev[i] = arr[i];
    sort(arr.begin(),arr.end());
    recalc();
}

int update(int i,int y){
    if(qsize++ == sq-4){
        qsize = 0;
        recalc();
    }
    return upd(i,y);
}

Compilation message (stderr)

elephants.cpp: In function 'void recalc()':
elephants.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

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