oj.uz

Submission #641421

# Submission time Handle Problem Language Result Execution time Memory
641421 2022-09-16T16:56:35 Z adrilen Dancing Elephants (IOI11_elephants) C++17
26 / 100
 5887 ms 9556 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 5e4 + 5;
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++;

        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()                                                 // 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)                         // 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5192 ms 1992 KB Output is correct
8 Correct 5402 ms 3400 KB Output is correct
9 Correct 5887 ms 6128 KB Output is correct
10 Runtime error 71 ms 9556 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5192 ms 1992 KB Output is correct
8 Correct 5402 ms 3400 KB Output is correct
9 Correct 5887 ms 6128 KB Output is correct
10 Runtime error 71 ms 9556 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5192 ms 1992 KB Output is correct
8 Correct 5402 ms 3400 KB Output is correct
9 Correct 5887 ms 6128 KB Output is correct
10 Runtime error 71 ms 9556 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -