제출 #998491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998491		bachhoangxuan	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	26 / 100	18 ms	18524 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 150005;
const int B = 400;

int N,L,S,V[maxn];
vector<vector<int>> X;
vector<vector<pii>> P;

void build(vector<int> &x,vector<pii> &p){
    int sz=(int)x.size();
    p.assign(sz,{0,0});
    int rt=sz;
    for(int i=sz-1;i>=0;i--){
        while(rt>0 && x[rt-1]>x[i]+L) rt--;
        if(rt==sz) p[i].fi=x[i];
        else p[i]=p[rt];
        p[i].se++;
    }
}

void init(int _N, int _L, int _X[])
{
    N=_N,L=_L;S=(N-1)/B+1;
    X.assign(S,{});P.assign(S,{});
    for(int i=0;i<N;i++) X[i/B].push_back(V[i]=_X[i]);
    for(int i=0;i<S;i++) build(X[i],P[i]);
}

void del(int val){
    int p=0;
    while(p<S && val>X[p].back()) p++;
    for(int i=0;i<(int)X[p].size();i++){
        if(X[p][i]==val){
            X[p].erase(X[p].begin()+i);
            break;
        }
    }
    //cout << p << ' ' << S << endl;
    //cout << "del " << p << endl;
    if(X[p].empty()){
        //cout << "empty" << '\n';
        X.erase(X.begin()+p);
        P.erase(P.begin()+p);
        S--;
    }
    else build(X[p],P[p]);
}

void add(int val){
    int p=0;
    while(p<S && val>X[p].back()) p++;
    if(p==S) p--;
    for(int i=0;i<=(int)X[p].size();i++){
        if(i==(int)X[p].size() || val<=X[p][i]){
            X[p].insert(X[p].begin()+i,val);
            break;
        }
    }
    /*
    for(auto v:X){
        assert(!v.empty());
        for(auto a:v) cout << a << ' ';
    }
    cout << endl;
    cout << "add " << val << endl;
    */
    if((int)X[p].size()==2*B){
        vector<int> nw(X[p].begin()+B,X[p].end());
        X[p].resize(B);
        X.insert(X.begin()+p+1,nw);
        P.insert(P.begin()+p+1,{});
        build(X[p],P[p]);
        build(X[p+1],P[p+1]);
        S++;
    }
    else build(X[p],P[p]);
}

int update(int i, int y)
{
    //cout << i << endl;
    del(V[i]);
    V[i]=y;
    add(V[i]);
    int res=1,cur=X[0][0];
    for(int i=0;i<S;i++){
        int nxt=upper_bound(X[i].begin(),X[i].end(),cur+L)-X[i].begin();
        if(nxt==(int)X[i].size()) continue;
        res+=P[i][nxt].se;
        cur=P[i][nxt].fi;
    }
    return res;
}

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