제출 #641749

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

elephants

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 160000;
const int r = sqrt(maxn), b = 1 + maxn / r;           // r blocks of size b
 
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(r + r ** 2)
    {
        pos.insert(upper_bound(pos.begin(), pos.end(), p), p);
        siz++;
        calc();
        //if (!split(grou)) calc();
    }
 
    void rem(const int &p)                                      // O(r + r**2)
    {
        pos.erase(lower_bound(pos.begin(), pos.end(), p));
        siz--;
        calc();
    }
 
    void calc()
    {
        cam = vector <pii> (siz + 1);
        cam[siz].first = 0;
        cam[siz].second = -1;

        int sind = siz - 1;

        int furthest = 1e9 + 5;
        int cnt = 0;
        for (int y = siz - 1; y >= 0; y--)
        {
            if (pos[y] < furthest) {
                cnt ++;
                furthest = pos[y] - l;
            }
            cam[y].first = cnt;

            while (pos[sind] > pos[y] + l) sind--;

            if (sind + 1 == siz) cam[y].second = pos[y] + l;
            else cam[y].second = cam[sind + 1].second;
        }
    }
    
    
    
    int find_group(int pos, vector <Node>&grou)                         // O(log(r))
    {
        int lower = 0, higher = grou.size() - 1, mid;
 
        while (lower != higher)
        {
            mid = (lower + higher + 1) >> 1;
            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)                                      //O(r + r**2)
    {
        if (siz < (b * 3) / 2) 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) + 1, 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()                       // O(n log(n / r) / r)
{
    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 - b; i += b)                                  // O(n + (n*r**2)/r)
    {
        groups[i / b].init(vector<int>(X + i, X + i + b));
    }
 
    groups[i / b].init(vector<int>(X + i, X + n));
    
}
 
int update(int i, int y)
{
    groups[groups[0].find_group(m[i], groups)].rem(m[i]);           // O(log(n/r) + r**2)
    m[i] = y;
 
    groups[groups[0].find_group(y, groups)].ins(y, groups);         // O(log(n/r) + r**2)
 
    return all();
}

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