Submission #804641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
804641	2023-08-03T10:39:26 Z	t6twotwo	Distributing Candies (IOI21_candies)	C++17	Compilation error	0 ms	0 KB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> mn, mn2, mx, mx2, lzad, lzmn, lzmx;
void apply_add(int p, ll v) {
    if (p >= mn.size()) {
        return;
    }
    lzad[p] += v;
    mn[p] += v;
    mx[p] += v;
    if (mn2[p] != inf) {
        mn2[p] += v;
    }
    if (mx2[p] != -inf) {
        mx2[p] += v;
    }
}
void apply_upd(int p, ll cmn, ll cmx) {
    if (p >= mn.size()) {
        return;
    }
    assert(cmn >= cmx);
    if (mn[p] == mx[p]) {
        if (cmn < mn[p]) {
            mn[p] = mx[p] = cmn;
            lzmn[p] = cmn;
        }
        if (cmx > mx[p]) {
            mx[p] = mn[p] = cmx;
            lzmx[p] = cmx;
        }
        return;
    }
    if (cmn > mx2[p] && cmn < mx[p]) {
        mx[p] = cmn;
        lzmn[p] = cmn;
    }
    if (cmx < mn2[p] && cmx > mn[p]) {
        mn[p] = cmx;
        lzmx[p] = cmx;
    }
}
void push_add(int p) {
    apply_add(p * 2, lzad[p]);
    apply_add(p * 2 + 1, lzad[p]);
    lzad[p] = 0;
}
void push_upd(int p) {
    apply_upd(p * 2, lzmn[p], lzmx[p]);
    apply_upd(p * 2 + 1, lzmn[p], lzmx[p]);
    lzmn[p] = inf;
    lzmx[p] = -inf;
}
void pull(int p) {
    int l = p * 2;
    int r = p * 2 + 1;
    mx[p] = max(mx[l], mx[r]);
    mn[p] = min(mn[l], mn[r]);
    mx2[p] = max(mx[p] == mx[l] ? mx2[l] : mx[l], mx[p] == mx[r] ? mx2[r] : mx[r]);
    mn2[p] = min(mn[p] == mn[l] ? mn2[l] : mn[l], mn[p] == mn[r] ? mn2[r] : mn[r]);
}
void add(int p, int l, int r, int L, int R, int v) {
    push_upd(p);
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply_add(p, v);
        return;
    }
    int m = (l + r + 1) / 2;
    push_add(p);
    add(p * 2, l, m, L, R, v);
    add(p * 2 + 1, m, r, L, R, v);
    pull(p);
}
void upd(int p, int l, int r, int L, int R, ll v, bool f) {
    push_add(p);
    if (R <= l || r <= L || (!f && v >= mx[p]) || (f && v <= mn[p])) {
        return;
    }
    if (L <= l && r <= R && (mn[p] == mx[p] || (!f && v > mx2[p]) || (f && v < mn2[p]))) {
        if (f) {
            apply_upd(p, inf, v);
        } else {
            apply_upd(p, v, -inf);
        }
        return;
    }
    int m = (l + r + 1) / 2;
    push_upd(p);
    upd(p * 2, l, m, L, R, v, f);
    upd(p * 2 + 1, m, r, L, R, v, f);
    pull(p);
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int N = C.size(), Q = V.size();
    int M = 2 << __lg(N - 1);
    mn.resize(2 * M, 0);
    mx.resize(2 * M, 0);
    mn2.resize(2 * M, inf);
    mx2.resize(2 * M, -inf);
    lzad.resize(2 * M);
    lzmn.resize(2 * M, inf);
    lzmx.resize(2 * M, -inf);
    for (int i = 0; i < Q; i++) {
        add(1, 0, M, L[i], R[i] + 1, V[i]);
        if (V[i] > 0) {
            upd(1, 0, M, L[i], R[i] + 1, C[0], 0);
        } else {
            upd(1, 0, M, L[i], R[i] + 1, 0, 1);
        }
    }
    for (int i = 1; i < M; i++) {
        assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
        push_add(i);
        push_upd(i);
    }
    vector<int> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] = mx[i + M];
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void apply_add(int, ll)':
candies.cpp:8:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if (p >= mn.size()) {
      |         ~~^~~~~~~~~~~~
candies.cpp: In function 'void apply_upd(int, ll, ll)':
candies.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (p >= mn.size()) {
      |         ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:118:38: error: no match for 'operator==' (operand types are 'std::vector<long long int>' and 'const ll' {aka 'const long long int'})
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                 ~~~~ ^~ ~~~
      |                                 |       |
      |                                 |       const ll {aka const long long int}
      |                                 std::vector<long long int>
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1035:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1035 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1035:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1131:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1131 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1131:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1206:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1206 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1206:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1298:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1298 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1298:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const ll' {aka 'const long long int'}
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1373:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1373 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1373:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1466:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1466 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1466:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const ll' {aka 'const long long int'}
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:1545:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1545 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1545:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from candies.cpp:2:
/usr/include/c++/10/bits/regex.h:2101:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 2101 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2101:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:466:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  466 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:466:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::pair<_T1, _T2>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  360 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:360:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  398 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:398:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1427 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1495 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/vector:64,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/allocator.h:206:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const std::allocator<_Tp1>&, const std::allocator<_T2>&)'
  206 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:206:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::allocator<_Tp1>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/vector:67,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1892:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator==(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
 1892 |     operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1892:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   mismatched types 'const std::vector<_Tp, _Alloc>' and 'const ll' {aka 'const long long int'}
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/postypes.h:222:5: note: candidate: 'template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  222 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:222:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:2:
candies.cpp:118:41: note:   'std::vector<long long int>' is not derived from 'const std::fpos<_StateT>'
  118 |         assert(lzad[i] == 0 || (lzmn == inf && lzmx == -inf));
      |                                         ^~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/string_view:490:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::basic_string_view<_CharT, _Traits>, std::b