Submission #939677

#	Time	Username	Problem	Language	Result	Execution time	Memory
939677		Sundavar	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	3018 ms	22932 KiB

elephants

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

using namespace std;
typedef pair<int,int> pii;
#define pos first
#define ind second
int at[(int)2e5];
struct buck{
    vector<pii> poz, inf;
};
const int S = 400;
int L, upd = 0;
buck bus[S];
int count(){
    int ans = 0, last = -1;
    for(int i = 0; i < S; i++){
        int j = upper_bound(bus[i].poz.begin(), bus[i].poz.end(), pii(last, 2e9)) - bus[i].poz.begin();
        if(j == bus[i].poz.size()) continue;
        ans += bus[i].inf[j].first, last = bus[i].inf[j].second;
    }
    return ans;
}
void updateBuck(buck& b){
    int last = b.poz.size();
    b.inf.clear(), b.inf.resize(last);
    for(int i = last-1; i >= 0; i--){
        while(b.poz[last-1].pos - b.poz[i].pos > L) last--;
        if(last == b.poz.size()) b.inf[i] = {1, b.poz[i].pos + L};
        else b.inf[i] = {b.inf[last].first + 1, b.inf[last].second};
    }
}
void beoszt(vector<pii>& els){
    for(int i = 0, d = 0, id = 0; i < els.size(); i++){
        if(++d == S) id++, d = 0;
        bus[id].poz.push_back(els[i]);
        at[els[i].ind] = id;
    }
    for(int i = 0; i < S; i++) updateBuck(bus[i]);
}
void remove(int from, int id){
    vector<pii> uj;
    for(pii& a : bus[from].poz)
        if(a.second != id) uj.push_back(a);
    bus[from].poz = uj;
    updateBuck(bus[from]);
}
void insert(int id, pii ele){
    vector<pii> uj;
    at[ele.ind] = id;
    for(pii& a : bus[id].poz){
        if(ele.first < a.first) uj.push_back(ele), ele = {2e9,-1};
        uj.push_back(a);
    }
    if(ele != pii(2e9, -1)) uj.push_back(ele);
    bus[id].poz = uj;
    updateBuck(bus[id]);
}
void init(int N, int l, int x[]){
    L = l;
    vector<pii> els(N);
    for(int i = 0; i < N; i++) els[i] = {x[i], i};
    beoszt(els);
}
int update(int i, int y){
    remove(at[i], i);
    int last = 0;
    for(int i = 0; i < S; i++)
        if(bus[i].poz.size() > 0 && y > bus[i].poz[0].pos) last = i;
    insert(last, pii(y, i));
    if(++upd%S == 0){
        vector<pii> els;
        for(int i = 0; i < S; i++){
            for(pii& a : bus[i].poz) els.push_back(a);
            bus[i].poz.clear();
        }
        beoszt(els);
    }
    return count();
}

/*int main(){
    int N, L, M;
    cin>>N>>L>>M;
    int x[N];
    for(int i = 0; i < N; i++) cin>>x[i];
    init(N,L,x);
    while(M--){
        int i, y;
        cin>>i>>y;
        cout<<update(i, y)<<"\n";
    }
}*/

Compilation message (stderr)

elephants.cpp: In function 'int count()':
elephants.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(j == bus[i].poz.size()) continue;
      |            ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void updateBuck(buck&)':
elephants.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(last == b.poz.size()) b.inf[i] = {1, b.poz[i].pos + L};
      |            ~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void beoszt(std::vector<std::pair<int, int> >&)':
elephants.cpp:34:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0, d = 0, id = 0; i < els.size(); i++){
      |                                   ~~^~~~~~~~~~~~

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