Submission #1292140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292140		enzy	Dancing Elephants (IOI11_elephants)	C++20	10 / 100	1 ms	572 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=150010;
const int sqtb=121; // qtd de buckets
const int sqtt=2; // qtd de caras no buckets
const int sqtq=500; // qtd de queries q precisa ter pra dar reset
const int inf=1e9+7;

int n, qtd_upd, l;
multiset<int>ms;
vector<pair<int,int>>buckets, at_lim; // guardando o ini e fim dos buckets
vector<vector<int>>caras;
pair<int,int> dp[sqtb][sqtt+10]; // dp[bucket][cara] = {cost,sobra}
int v[maxn];

void init(int N, int L, int X[]){
    n=N; l=L;
    for(int i=0;i<N;i++){
        v[i]=X[i];
        ms.insert(X[i]);
    }
}

void colocar(int i, int x){
    vector<int>aux;
    while(caras[i].size()&&x<=caras[i].back()){
        aux.push_back(caras[i].back());
        caras[i].pop_back();
    }
    caras[i].push_back(x);
    while(aux.size()){
        caras[i].push_back(aux.back());
        aux.pop_back();
    }
}

void tirar(int i, int x){
    vector<int>aux;
    while(caras[i].size()&&x<=caras[i].back()){
        aux.push_back(caras[i].back());
        caras[i].pop_back();
    }
    aux.pop_back(); // tirando um dos x
    while(aux.size()){
        caras[i].push_back(aux.back());
        aux.pop_back();
    }
}

void recalc(int i){ // recalculo a dp do bucket i
    for(int j=0;j<caras[i].size();j++) dp[i][j]={inf,0};
    for(int j=caras[i].size()-1;j>=0;j--){
        int at=caras[i][j];
        int sobra=l-(buckets[i].second-at), cost=1;
        if(caras[i].back()>at+l){ // vendo se eu cubro o ultimo cara
            int id=upper_bound(caras[i].begin(),caras[i].end(),at+l)-caras[i].begin(); // pegando o id do primeiro cara q n cubro do bucket
            cost=dp[i][id].first+1;
        }
        if(dp[i][j].first>cost) dp[i][j]={cost,sobra};
        else if(dp[i][j].first==cost&&dp[i][j].second<sobra) dp[i][j]={cost,sobra};
    }


    // cerr << "dp of " << i << ": " << endl;
    // for(int j=0;j<caras[i].size();j++) cerr << dp[i][j].first << " " << dp[i][j].second << endl;
    // cerr << endl;
}

int simular(){
    // cout << "! enter " << buckets.size() << endl;
    int id=-1, resp=0;
    for(int i=0;i<buckets.size();i++){
        // cout << buckets[i].first << " " << buckets[i].second << endl;
        if(caras[i].empty()) continue; // n tem ninguem pra cobrir
        if(buckets[i].second<=id) continue; // n preciso aumentar a resposta, ja q o outro intervalo cobre tudo
        int at=upper_bound(caras[i].begin(),caras[i].end(),id)-caras[i].begin();
        // cout << "! " << at << " " << dp[i][at].first << endl;
        resp+=dp[i][at].first;
        id=buckets[i].second+dp[i][at].second;
    }
    return resp;
}

int update(int i, int y){
    // att o multiset, para qnd precisar dar recalc em tds
    int ant=v[i];
    ms.erase(ms.find(v[i]));
    v[i]=y;
    ms.insert(v[i]);
    if((qtd_upd%sqtq)==0){ // reconstruir os buckets
        // cerr << "recalc all" << endl;
        buckets.clear(); caras.clear();
        int cnt=-1, ini=-1, qtd=0;
        // for(int x : ms) cout << x << ' ';
        // cout << endl;
        vector<int>aux;
        for(int x : ms){
            cnt++;
            // cerr << cnt << " " << x << endl;
            if(!cnt) ini=x;
            // caras[cnt].push_back(x);
            aux.push_back(x);
            if(cnt==sqtt){
                if(qtd) buckets.push_back({ini,x});
                else buckets.push_back({-1,x});
                caras.push_back(aux);
                aux.clear();
                qtd++;
            }
            cnt%=sqtt;
        }
        // cerr << "orz" << endl;
        if(cnt){
            if(qtd) buckets.push_back({ini,inf});
            else buckets.push_back({-1,inf});
            caras.push_back(aux);
        }
        for(int i=0;i<buckets.size();i++) recalc(i);
    }else{
        // cerr << "substituting: " << endl;
        bool ok1=false, ok2=false;
        for(int i=0;i<buckets.size();i++){
            if(buckets[i].first<=y&&y<=buckets[i].second&&ok1==false){
                ok1=true;
                colocar(i,y);
                // if(caras[i].empty()) buckets[i].first=buckets[i].second=-1;
                // else buckets[i].first=caras[i][0]; buckets[i].second=caras[i].back(); // atualizando as pontas
                // cerr << "recalc only " << i << ": " << endl;
                recalc(i);
            }
            if(caras[i].size()&&caras[i][0]<=ant&&ant<=caras[i].back()&&ok2==false){
                ok2=true;
                tirar(i,ant);
                // if(caras[i].empty()) buckets[i].first=buckets[i].second=-1;
                // else buckets[i].first=caras[i][0]; buckets[i].second=caras[i].back(); // atualizando as pontas
                // cerr << "recalc only " << i << ": " << endl;
                recalc(i);
            }
        }
    }
    qtd_upd++;
    return simular();
}

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