Submission #565660

#	Time	Username	Problem	Language	Result	Execution time	Memory
565660		qwerasdfzxcl	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	18 ms	2512 KiB

elephants

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

using namespace std;
typedef long long ll;
const int INF = 1e9+100, B = 400;
int l;
struct Bucket{
    vector<pair<int, int>> X;
    vector<int> dp, dp2;
    Bucket(){}

    void push(int x, int ii, bool _ins = 0){
        if (!_ins) {X.emplace_back(x, ii); return;}

        for (int i=0;i<(int)X.size();i++) if (x <= X[i].first){
            X.insert(X.begin()+i, make_pair(x, ii));
            return;
        }
        X.insert(X.end(), make_pair(x, ii));
    }
    void _delete(int x, int i){
        for (auto iter = X.begin();iter!=X.end();iter++){
            if (iter->first==x && iter->second==i){
                X.erase(iter);
                return;
            }
        }
        //for (auto &p:X) printf("[%d %d] ", p.first, p.second);
        //printf("\n%d %d\n", x, i);
        assert(0);
    }
    void build(){
        dp.clear();
        dp2.clear();
        dp.resize(X.size(), -1);
        dp2.resize(X.size(), 1);

        int pt = (int)X.size()-1;
        for (int i=(int)X.size()-1;i>=0;i--){
            while(pt>i && X[i].first + l < X[pt].first) pt--;
            if (pt+1==(int)X.size()) {dp[i] = X[i].first; continue;}

            dp[i] = dp[pt+1];
            dp2[i] = dp2[pt+1] + 1;
        }
    }

    pair<int, int> get_nxt(int prv){
        auto iter = lower_bound(X.begin(), X.end(), make_pair(prv+l+1, -1));
        if (iter==X.end()) return {0, prv};
        int i = iter - X.begin();
        return {dp2[i], dp[i]};
    }
}buc[404];

const int BQ = 400;
int n, a[150150], bidx[150150], q, cntq = 0, cntb;
set<pair<int, int>> st;

void rebuild(){
    auto iter = st.begin();
    for (int i=0;true;i++){
        //printf(" YYES\n");
        buc[i].X.clear();

        for (int j=0;j<B;j++){
            if (iter==st.end()) break;
            buc[i].push(iter->first, iter->second);
            bidx[iter->second] = i;
            ++iter;
        }

        buc[i].build();
        cntb = i+1;
        if (iter==st.end()) break;
    }
}

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

    //printf("YES\n");
    rebuild();
}

int update(int I, int y)
{
    //printf("YES\n");
    if (n==1) return 1;

    I++;
    if (cntq==BQ){
        cntq = 0; rebuild();
    }
    cntq++;

    ///delete
    buc[bidx[I]]._delete(a[I], I);
    st.erase(st.find(make_pair(a[I], I)));
    buc[bidx[I]].build();

    ///push
    a[I] = y;
    auto iter = st.insert(make_pair(a[I], I)).first;
    if (iter==st.end()) bidx[I] = bidx[prev(iter)->second];
    else bidx[I] = bidx[next(iter)->second];
    buc[bidx[I]].push(a[I], I, 1);
    buc[bidx[I]].build();

    ///calculate
    int s = -INF, ans = 0;
    for (int i=0;i<cntb;i++){
        auto [cnt, nxt] = buc[i].get_nxt(s);
        ans += cnt;
        s = nxt;
    }

    //printf(" %d\n", ans);
    //for (auto &p:buc[0].X) printf("[%d %d] ", p.first, p.second);
    //printf("\n");
    return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:119:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |         auto [cnt, nxt] = buc[i].get_nxt(s);
      |              ^

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