제출 #764474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764474		boris_mihov	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	50 / 100	3643 ms	5932 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 = 20000;
const int MAXN = 150000 + 10;
const int INF  = 2e9;
 
int n, len;
int a[MAXN];
int x[MAXN];
int cycleTo;
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 = 7 * sqrt(n);
    cycleTo = n / bucketSize;

    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 / bucketSize].push_back(a[i]);
        ms.insert(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];
    }
    
    ms.clear();
    for (int i = 0 ; i <= cycleTo ; ++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 / bucketSize].push_back(a[i]);
        ms.insert(a[i]);
    }
 
    for (int i = 0 ; i <= cycleTo ; ++i)
    {
        std::sort(nums[i].begin(), nums[i].end());
        fix(i);
    }
}
 
int update(int idx, int y)
{
    for (int i = 0 ; i <= cycleTo ; ++i)
    {
        if (nums[i].size() > n / 4)
        {
            rebuild();
            break;
        }
    }
 
    idx++;
    ms.erase(ms.find(x[idx]));
    if (!ms.count(x[idx]))
    {
        for (int i = 0 ; i <= cycleTo ; ++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 <= cycleTo ; ++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]);
        }
    }

    ms.insert(y);

    int res = 0;
    int coveredTo = -1;
    for (int bucket = 0 ; bucket <= cycleTo ; ++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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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