Submission #110382

#	Time	Username	Problem	Language	Result	Execution time	Memory
110382		doowey	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6681 ms	17044 KiB

elephants

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MAXN = 150004;
const int B = 512;

struct Data{
    int pos;
    int jumpl;
    int nexp;
    bool operator<(const Data &D) const {
        return pos < D.pos;
    }
};

vector<Data> Q[MAXN];
int n;
int bl;
int len;

void compute(int id){
    if(Q[id].empty())
        return;
    int sz = Q[id].size();
    int lp = sz - 1;
    for(int i = sz - 1; i >= 0 ; i -- ){
        while(Q[id][lp].pos - Q[id][i].pos > len){
            -- lp;
        }
        if(lp == sz - 1){
            Q[id][i].jumpl = 1;
            Q[id][i].nexp = Q[id][i].pos + len;
        }
        else{
            Q[id][i].jumpl = Q[id][lp + 1].jumpl + 1;
            Q[id][i].nexp = Q[id][lp + 1].nexp;
        }
    }
}

int pz[MAXN];

int oper = 1;

void init(int N, int L, int X[]){
    n = N;
    len = L;
    bl = (n + B - 1) / B;
    for(int i = 0 ; i < n ; i ++ )
        pz[i] = X[i];
    for(int i = 0 ; i < n ; i ++ ){
        Q[i/B].push_back({X[i], -1, -1});
    }
    for(int i = 0 ; i < bl ; i ++ )
        compute(i);
}

bool check(int id ,int el){
    if(Q[id].empty())
        return false;
    Data W = {el, -1, -1};
    int sd = lower_bound(Q[id].begin() ,Q[id].end(), W) - Q[id].begin();
    if(sd < Q[id].size()){
        return Q[id][sd].pos == el;
    }
    return false;
}

void Erase(int el){
    int id = -1;
    for(int i = bl - 1; i >= 0 ; i -- ){
        if(Q[i].empty())continue;
        if(check(i, el)){
            id = i;
            break;
        }
    }
    vector<int> idx;
    bool er = false;
    for(auto p : Q[id]){
        if(p.pos == el){
            if(er){
                idx.push_back(p.pos);
            }
            else{
                er=true;
            }
        }
        else{
            idx.push_back(p.pos);
        }
    }
    Q[id].clear();
    for(auto v : idx){
        Q[id].push_back({v, -1, -1});
    }
    compute(id);
}

void Insert(int el){
    int id = 0;
    for(int i = bl - 1; i >= 0 ; i -- ){
        if(Q[i].empty()) continue;
        if(el >= Q[i][0].pos){
            id = i;
            break;
        }
    }
    vector<int> ver;
    for(auto p : Q[id]){
        if(el <= p.pos && el != -1){
            ver.push_back(el);
            el = -1;
        }
        ver.push_back(p.pos);
    }
    if(el!=-1)
        ver.push_back(el);
    Q[id].clear();
    for(auto p : ver)
        Q[id].push_back({p,-1,-1});
    compute(id);
}

int update(int i, int y){
    oper ++ ;
    oper %= B;
    if(oper == 0){
        vector<int> tot;
        for(int j = 0 ; j < bl ; j ++ ){
            for(auto p : Q[j])
                tot.push_back(p.pos);
            Q[j].clear();
        }
        for(int j = 0 ; j < n; j ++ ){
            Q[j / B].push_back({tot[j], -1, -1});
        }
        for(int j = 0 ; j < bl; j ++ ) compute(j);
    }
    Erase(pz[i]);
    pz[i]=y;
    Insert(pz[i]);
    int endp = -1;
    int res = 0;
    int rd;
    Data C;
    for(int j = 0 ; j < bl ; j ++ ){
        if(Q[j].empty())
            continue;
        C = {endp, -1, -1};
        rd = upper_bound(Q[j].begin(), Q[j].end(), C) - Q[j].begin();
        if(rd < Q[j].size()){
            res += Q[j][rd].jumpl;
            endp = Q[j][rd].nexp;
        }
    }
    return res;
}

Compilation message (stderr)

elephants.cpp: In function 'bool check(int, int)':
elephants.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sd < Q[id].size()){
        ~~~^~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:161:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(rd < Q[j].size()){
            ~~~^~~~~~~~~~~~~

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