oj.uz

답안 #641748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641748 2022-09-17T14:23:05 Z adrilen 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 2689 ms 9532 KB 
#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++;
 
        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);
 
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 869 ms 2712 KB Output is correct
8 Correct 1079 ms 3368 KB Output is correct
9 Correct 2689 ms 5932 KB Output is correct
10 Runtime error 59 ms 9532 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 869 ms 2712 KB Output is correct
8 Correct 1079 ms 3368 KB Output is correct
9 Correct 2689 ms 5932 KB Output is correct
10 Runtime error 59 ms 9532 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 869 ms 2712 KB Output is correct
8 Correct 1079 ms 3368 KB Output is correct
9 Correct 2689 ms 5932 KB Output is correct
10 Runtime error 59 ms 9532 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -