Submission #821632

#	Time	Username	Problem	Language	Result	Execution time	Memory
821632		annabeth9680	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	1 ms	340 KiB

elephants

#include "elephants.h" 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+5;
int arr[MAXN],n,l,pos[MAXN]; //bucket i is in
bool cmp(int x, int y){
    return arr[x]<arr[y];
}
struct bucket{
    vector<vector<int>> vec,nxt,fotos;
    void build(){
        vector<int> ind;
        for(int i = 1;i<=n;++i) ind.push_back(i);
        sort(ind.begin(),ind.end(),cmp);
        int id = 0, b = 0;
        while(id < n){
            b++;
            if(b == 1) vec.push_back({});
            vec.back().push_back(ind[id]);
            pos[ind[id]] = vec.size()-1;
            id++;
            if(b >= 500) b = 0;
        }
        for(int i = 0;i<vec.size();++i){
            vector<int> v(2505);
            fotos.push_back(v); nxt.push_back(v);
            int cur = vec[i].size()-1;
            for(int j = vec[i].size()-1;j >= 0;--j){
                while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
                if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                    fotos[i][j] = 1;
                    nxt[i][j] = arr[vec[i][j]]+l+1;
                }
                else{
                    fotos[i][j] = fotos[i][cur]+1;
                    nxt[i][j] = nxt[i][cur];
                }
            }
        }
    }
    int query(){
        int lo = -INF, ans = 0;
        for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
            int l = 0, r = vec[i].size()-1, erg = -1;
            while(l < r){
                int mid = (l+r)/2;
                if(arr[vec[i][mid]] >= lo){
                    erg = mid;
                    r = mid;
                }
                else{
                    l = mid+1;
                }
            }
            if(erg == -1) continue;
            ans += fotos[i][erg]; lo = nxt[i][erg];
        }
        return ans;
    }
    void ins(int id){
        int bnum = 0;
        for(int i = vec.size()-1;i>=0;--i){
            if(vec[i][0] <= arr[id]){
                bnum = i;
                break;
            }
        }
        bool good = false;
        for(int i = 0;i<vec[bnum].size();++i){
            if(vec[bnum][i] > arr[id]){
                vec[bnum].insert(vec[bnum].begin()+i,id);
                good = true;
                break;
            }
        }
        if(!good) vec[bnum].push_back(id);
        int i = bnum;
        int cur = vec[i].size()-1;
        for(int j = vec[i].size()-1;j >= 0;--j){
            while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
            if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                fotos[i][j] = 1;
                nxt[i][j] = arr[vec[i][j]]+l+1;
            }
            else{
                fotos[i][j] = fotos[i][cur]+1;
                nxt[i][j] = nxt[i][cur];
            }
        }
    }
    void del(int id){
        int bnum = pos[id];
        for(int i = 0;i<vec[bnum].size()-1;++i){
            if(vec[bnum][i] == id){
                vec[bnum].erase(vec[bnum].begin()+i);
                break;
            }
        }
        int i = bnum;
        int cur = vec[i].size()-1;
        for(int j = vec[i].size()-1;j >= 0;--j){
            while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
            if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                fotos[i][j] = 1;
                nxt[i][j] = arr[vec[i][j]]+l+1;
            }
            else{
                fotos[i][j] = fotos[i][cur]+1;
                nxt[i][j] = nxt[i][cur];
            }
        }
    }
};
int curq; bucket eimer;
void init(int N, int L, int X[]){
    n = N; l = L;
    for(int i = 1;i<=N;++i) arr[i] = X[i-1];
    eimer.build();
    curq = 490;
}
int update(int i, int y){
    if(curq == 0){
        eimer.build();
        curq = 490;
    }
    else{
        eimer.del(i+1);
        arr[i+1] = y;
        eimer.ins(i+1);
    }
    return eimer.query();
}

Compilation message (stderr)

elephants.cpp: In member function 'void bucket::build()':
elephants.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = 0;i<vec.size();++i){
      |                       ~^~~~~~~~~~~
elephants.cpp: In member function 'int bucket::query()':
elephants.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
      |                       ~^~~~~~~~~~~
elephants.cpp: In member function 'void bucket::ins(int)':
elephants.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i = 0;i<vec[bnum].size();++i){
      |                       ~^~~~~~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::del(int)':
elephants.cpp:94:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i = 0;i<vec[bnum].size()-1;++i){
      |                       ~^~~~~~~~~~~~~~~~~~~

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