Submission #641330

#	Time	Username	Problem	Language	Result	Execution time	Memory
641330		adrilen	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9087 ms	2004 KiB

elephants

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 1.5e5;
const int r = sqrt(maxn) + 1, b = maxn / r;

map<int, int> m;
int n, l;


struct Node {
    int siz;
    // Positions of the elephants sorted. First is first element, last is last element

    // Number of cameras starting in this group given that a number of elephants in allready 
    // acounted for
    vector <pii> cam;
    // cam[i] means number of cameras needed given that i-th elephant is first we need
    
    vector <int> pos;
    void init(const vector <int> &positions)
    {
        pos = positions;
        siz = positions.size();
        calc();
    }

    void ins(const int &p, vector <Node>&grou)                 // O(n)
    {
        pos.insert(upper_bound(pos.begin(), pos.end(), p), p);
        siz++;

        if (!split(grou)) calc();
    }

    void rem(const int &p)                 // O(n)
    {
        pos.erase(lower_bound(pos.begin(), pos.end(), p));
        siz--;
        calc();
    }

    void calc()                     // O(r**2 )
    {
        cam = vector <pii> (siz + 1);
        cam[siz].first = 0;                 // All elephants are covered
        cam[siz].second = -1;

        int furthest;
        for (int y = 0; y < siz; y++)
        {
            furthest = -1;
            for (int i = y; i < siz; i++)
            { 
                if (pos[i] > furthest)
                {
                    furthest = pos[i] + l;
                    cam[y].first++;
                }
            }
            cam[y].second = furthest;
        }
    }
    
    int find_group(int pos, vector <Node>&grou)
    {
        int lower = 0, higher = grou.size() - 1, mid;

        while (lower != higher)
        {
            mid = (lower + higher + 1) >> 1;
            // cout << lower << " " << mid << " " << higher << endl;
            if (grou[mid].pos.size() == 0 || grou[mid].pos[0] > pos) higher = mid - 1;
            else lower = mid;
        }
        return lower;
    }

    // Function for splitting the group if it is 2r in size
    bool split(vector <Node>&grou)
    {
        if (siz < (r * 4) / 3) return false;

        Node new_group;

        int mid = siz / 2;
        new_group.init(vector<int>(pos.begin() + mid, pos.end()));
        grou.insert(grou.begin() + find_group(pos[0], grou), new_group);
        
        pos.resize(mid);
        siz = mid;
        calc();

        return true;
    }
} ; 


vector <Node> groups(r);


void print_groups()
{
    cout << r << "\n";
    for (int i = 0; i < r; i++)
    {
        cout << i << "\n";
        cout << groups[i].siz << "\n";

        if (groups[i].siz == 0) continue;

        for (int q : groups[i].pos) cout << q << " ";
        cout << "\n";
        for (pii q : groups[i].cam) cout << q.first << " ";
        cout << "\n";
        for (pii q : groups[i].cam) cout << q.second << " ";
        cout << "\n\n";
    }
}

int all()
{
    int out = 0,
    furthest = -1,
    pos;


    for (auto g : groups) {
        if (g.siz == 0) continue;
        
        pos = upper_bound(g.pos.begin(), g.pos.end(), furthest) - g.pos.begin();

        out += g.cam[pos].first;
        furthest = max(furthest, g.cam[pos].second);
    }
    return out;
}

void init(int N, int L, int X[])
{
    n = N, l = L;

    // Keeping track of the positions of the elephants by number
    for (int i = 0; i < n; i++)             // O(n log(n))
    {
        m.insert(pii(i, X[i]));
    }

    int i;
    for (i = 0; i < n - r; i += r) 
    {
        groups[i / r].init(vector<int>(X + i, X + i + r));
    }

    groups[i / r].init(vector<int>(X + i, X + n));
    
}

int update(int i, int y)
{
    groups[groups[0].find_group(m[i], groups)].rem(m[i]);
    m[i] = y;

    groups[groups[0].find_group(y, groups)].ins(y, groups);

    return all();
}

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