Submission #1293312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293312		Sofiatpc	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	5672 ms	14032 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 150005;
int suf[MAXN], x[MAXN], extra[MAXN], marc[MAXN], n, tam = 1250, l, cur;
set<pair<int,int>> st;
vector< vector< pair<int,int> > > buckets;

void fazbucket(int i){
    int lst = buckets[i].size()-1;
    for(int j = buckets[i].size()-1; j >= 0; j--){
        while(buckets[i][lst].fi - buckets[i][j].fi > l)lst--;

        if(lst+1 < buckets[i].size()){
            suf[ buckets[i][j].sc ] = suf[ buckets[i][lst+1].sc ] + 1;
            extra[ buckets[i][j].sc ] = extra[ buckets[i][lst+1].sc ];
        }else{
            suf[ buckets[i][j].sc ] = 1;
            extra[ buckets[i][j].sc ] = buckets[i][j].fi + l;
        }
    }
}

void faz(){
    auto it = st.rbegin();
    buckets.clear();
    int qtd = 0, b = 0; buckets.push_back({});
    while(it != st.rend()){
        if(qtd == tam){
            reverse(buckets[b].begin(),buckets[b].end());
            fazbucket(b);
            buckets.push_back({});
            qtd = 0; b++;
        }
        qtd++;
        marc[it->sc] = b;
        buckets[b].push_back(*it);
        it++;
    }
    reverse(buckets[b].begin(),buckets[b].end());
    fazbucket(b);
}

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

  faz();
}

int update(int i, int y)
{
    cur++;
    if(cur == 387){
        st.erase({x[i],i});
        x[i] = y;
        st.insert({x[i],i});
        cur = 0;
        faz();
    }else{
        st.erase({x[i],i});
        for(int j = 0; j < buckets[ marc[i] ].size(); j++)
            if(buckets[ marc[i] ][j].sc == i){ buckets[ marc[i] ].erase(buckets[marc[i]].begin()+j); break; }
        fazbucket(marc[i]);

        x[i] = y;
        st.insert({x[i],i});
        marc[i] = buckets.size()-1;
        for(int j = 0; j < buckets.size(); j++)
            if(buckets[j][0].fi <= x[i]){ marc[i] = j; break; }

        for(int j = buckets[ marc[i] ].size()-1; j >= -1; j--)
            if(j == -1 || buckets[ marc[i] ][j].fi < x[i]){ buckets[ marc[i] ].insert(buckets[marc[i]].begin()+j+1, {x[i],i} ); break; }
        fazbucket(marc[i]);
    }

    int ii = st.begin()->sc, ans = 0;
    while(1){
        ans += suf[ii];
        auto it = st.upper_bound({extra[ii], 100000000});
        if(it == st.end())break;
        ii = it->sc;
    }

  return ans;
}

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