Submission #764471

#	Time	Username	Problem	Language	Result	Execution time	Memory
764471		boris_mihov	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9061 ms	5000 KiB

elephants

#include "elephants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <cmath>
#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];
int bucketSize;
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;
    bucketSize = sqrt(n);

    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = a[i] = X[i - 1];
    }
 
    for (int i = 1 ; i <= n ; ++i)
    {
        nums[i / bucketSize].push_back(a[i]);
    }
 
    for (int i = 0 ; i <= n / bucketSize ; ++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)
    {
        nums[i / bucketSize].push_back(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 / 4)
        {
            rebuild();
            break;
        }
    }
 
    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;
    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])
        {
            inserted = true;
            insert(i, x[idx]);
        }
    }
 
    if (!inserted)
    {
        insert(lastBucket, x[idx]);
    }
 
    int res = 0;
    int coveredTo = -1;
    for (int bucket = 0 ; bucket <= n / bucketSize ; ++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 (stderr)

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

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