oj.uz

Submission #764430

# Submission time Handle Problem Language Result Execution time Memory
764430 2023-06-23T11:55:58 Z boris_mihov Dancing Elephants (IOI11_elephants) C++17
Compilation error
 0 ms 0 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 = 1005;
const int MAXN = 150000 + 10;
const int INF  = 2e9;

int n, len;
int a[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)
    {
        a[i] = X[i - 1];
        if (!ms.count(a[i]))
        {
            nums[a[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)
{
    idx++;
    ms.erase(ms.find(a[idx]));
    if (!ms.count(a[idx]))
    {
        erase(a[idx] / BUCKET_SIZE, a[idx]);
    }

    a[idx] = y;
    if (!ms.count(y))
    {
        insert(y / BUCKET_SIZE, y);
    }

    ms.insert(y);

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

        std::sort(nums[bucket].begin(), nums[bucket].back());
        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:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (ptr == nums[idx].size())
      |             ~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void erase(int, int)':
elephants.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0 ; i < nums[idx].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void insert(int, int)':
elephants.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0 ; i < nums[idx].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:128:60: error: no matching function for call to 'sort(std::vector<int>::iterator, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
  128 |         std::sort(nums[bucket].begin(), nums[bucket].back());
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4849:5: note: candidate: 'template<class _RAIter> void std::sort(_RAIter, _RAIter)'
 4849 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4849:5: note:   template argument deduction/substitution failed:
elephants.cpp:128:60: note:   deduced conflicting types for parameter '_RAIter' ('__gnu_cxx::__normal_iterator<int*, std::vector<int> >' and 'int')
  128 |         std::sort(nums[bucket].begin(), nums[bucket].back());
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4880:5: note: candidate: 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
 4880 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4880:5: note:   template argument deduction/substitution failed:
elephants.cpp:128:60: note:   deduced conflicting types for parameter '_RAIter' ('__gnu_cxx::__normal_iterator<int*, std::vector<int> >' and 'int')
  128 |         std::sort(nums[bucket].begin(), nums[bucket].back());
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:74,
                 from elephants.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:292:1: note: candidate: 'template<class _ExecutionPolicy, class _RandomAccessIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Compare)'
  292 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:292:1: note:   template argument deduction/substitution failed:
elephants.cpp:128:60: note:   candidate expects 4 arguments, 2 provided
  128 |         std::sort(nums[bucket].begin(), nums[bucket].back());
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:74,
                 from elephants.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: candidate: 'template<class _ExecutionPolicy, class _RandomAccessIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator)'
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note:   template argument deduction/substitution failed:
elephants.cpp:128:60: note:   candidate expects 3 arguments, 2 provided
  128 |         std::sort(nums[bucket].begin(), nums[bucket].back());
      |                                                            ^