oj.uz

Submission #764459

# Submission time Handle Problem Language Result Execution time Memory
764459 2023-06-23T12:23:03 Z boris_mihov Dancing Elephants (IOI11_elephants) C++17
0 / 100
 1 ms 596 KB 
#include "elephants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <set>

typedef long long llong;
const int MAXNUM = 1000000000;
const int BUCKET_SIZE = 2000;
const int MAXN = 150000 + 10;
const int INF  = 2e9;

int n, len;
int a[MAXN];
int x[MAXN];
std::vector <int> nums[BUCKET_SIZE];
std::vector <std::pair <int,int>> dp[BUCKET_SIZE];

void fix(int idx)
{
    dp[idx].resize(nums[idx].size());
    int ptr = nums[idx].size();

    for (int i = (int)nums[idx].size() - 1 ; i >= 0 ; --i)
    {
        while (ptr > 0 && nums[idx][i] + len < nums[idx][ptr - 1])
        {
            ptr--;
        }

        if (ptr == nums[idx].size())
        {
            dp[idx][i] = {1, nums[idx][i] + len};
        } else
        {
            dp[idx][i] = dp[idx][ptr];
            dp[idx][i].first++;
        }
    }
}

void erase(int idx, int val)
{
    for (int i = 0 ; i < nums[idx].size() ; ++i)
    {
        if (nums[idx][i] == val)
        {
            nums[idx].erase(nums[idx].begin() + i);
            break;
        }
    }

    fix(idx);
}

void insert(int idx, int val)
{
    bool inserted = false;
    for (int i = 0 ; i < nums[idx].size() ; ++i)
    {   
        if (val < nums[idx][i])
        {
            nums[idx].insert(nums[idx].begin() + i, val);
            inserted = true;
            break;
        }
    }   

    if (!inserted)
    {
        nums[idx].push_back(val);
    }

    fix(idx);
}

std::multiset <int> ms;
void init(int N, int L, int X[])
{
    n = N;
    len = L;

    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = a[i] = X[i - 1];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (!ms.count(a[i])) nums[i / BUCKET_SIZE].push_back(a[i]);
        ms.insert(a[i]);
    }

    for (int i = 0 ; i < BUCKET_SIZE ; ++i)
    {
        std::sort(nums[i].begin(), nums[i].end());
        fix(i);
    }
}

void rebuild()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = x[i];
    }

    for (int i = 0 ; i < BUCKET_SIZE ; ++i)
    {   
        nums[i].clear();
    }

    std::sort(a + 1, a + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!ms.count(a[i])) nums[i / BUCKET_SIZE].push_back(a[i]);
        ms.insert(a[i]);
    }

    for (int i = 0 ; i < BUCKET_SIZE ; ++i)
    {
        std::sort(nums[i].begin(), nums[i].end());
        fix(i);
    }
}

int update(int idx, int y)
{
    for (int i = 0 ; i < BUCKET_SIZE ; ++i)
    {
        if (nums[i].size() > n / 2)
        {
            rebuild();
            break;
        }
    }

    idx++;
    ms.erase(x[idx]);
    if (!ms.count(x[idx]))
    {
        for (int i = 0 ; i < BUCKET_SIZE ; ++i)
        {
            if (nums[i].empty())
            {
                continue;
            }

            if (nums[i][0] <= x[idx] && x[idx] <= nums[i].back())
            {
                erase(i, x[idx]);
                break;
            }
        }
    }

    x[idx] = y;

    if (!ms.count(y))
    {
        bool inserted = false;
        int lastBucket = -1;
        for (int i = 0 ; i < BUCKET_SIZE ; ++i)
        {
            if (nums[i].empty())
            {
                continue;
            }

            lastBucket = i;
            if (nums[i][0] <= x[idx] && x[idx] <= nums[i].back())
            {
                inserted = true;
                insert(i, x[idx]);
                break;
            }

            if (nums[i][0] > x[idx])
            {
                if (i == 0)
                {
                    inserted = true;
                    insert(i, x[idx]);
                }
            }
        }

        if (!inserted)
        {
            insert(lastBucket, x[idx]);
        }
    }

    ms.insert(y);

    int res = 0;
    int coveredTo = -1;
    for (int bucket = 0 ; bucket <= 100 ; ++bucket)
    {
        if (nums[bucket].empty())
        {
            continue;
        }

        if (coveredTo >= nums[bucket].back())
        {
            continue;
        }
        
        int l = -1, r = nums[bucket].size() - 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (nums[bucket][mid] <= coveredTo) l = mid;
            else r = mid;
        }

        res += dp[bucket][r].first;
        coveredTo = dp[bucket][r].second;
    }

    return res;
}

Compilation message

elephants.cpp: In function 'void fix(int)':
elephants.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (ptr == nums[idx].size())
      |             ~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void erase(int, int)':
elephants.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0 ; i < nums[idx].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void insert(int, int)':
elephants.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0 ; i < nums[idx].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:134:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |         if (nums[i].size() > n / 2)
      |             ~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -