Submission #1277506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277506		k12_khoi	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second

const int N = 500000 + 5;
const int mod = 1000000007;
const int limit = 1000000000;

int n, request, type, x, y, u, v, k;
int a[N], b[N], Xarr[N], Yarr[N], t[4 * N], lazy[4 * N], tTwo[4 * N];
set<int> se;
set<int>::iterator it;

int mul(int x, int y) {
    return int((1LL * x * y) % mod);
}

int luythua(int x, int nexp) {
    int c = 1;
    while (nexp) {
        if (nexp & 1) c = mul(c, x);
        x = mul(x, x);
        nexp >>= 1;
    }
    return c;
}

void down(int id) {
    if (lazy[id] != 1) {
        lazy[id << 1] = mul(lazy[id << 1], lazy[id]);
        lazy[id << 1 | 1] = mul(lazy[id << 1 | 1], lazy[id]);

        tTwo[id << 1] = mul(tTwo[id << 1], lazy[id]);
        tTwo[id << 1 | 1] = mul(tTwo[id << 1 | 1], lazy[id]);

        lazy[id] = 1;
    }
}

// update_range uses globals u,v,k like original
void update_range(int id, int l, int r) {
    if (u > r || v < l) return;
    if (u <= l && r <= v) {
        tTwo[id] = mul(tTwo[id], k);
        lazy[id] = mul(lazy[id], k);
        return;
    }
    down(id);
    int m = (l + r) >> 1;
    update_range(id << 1, l, m);
    update_range(id << 1 | 1, m + 1, r);
}

// update_point uses globals u,k: set t at leaf u to k
void update_point(int id, int l, int r) {
    if (l == r) {
        t[id] = k;
        return;
    }
    int m = (l + r) >> 1;
    if (u <= m) update_point(id << 1, l, m);
    else update_point(id << 1 | 1, m + 1, r);
    t[id] = max(t[id << 1], t[id << 1 | 1]);
}

// get_range uses globals u,v
int get_range(int id, int l, int r) {
    if (u > r || v < l) return 0;
    if (u <= l && r <= v) return t[id];
    down(id);
    int m = (l + r) >> 1;
    return max(get_range(id << 1, l, m), get_range(id << 1 | 1, m + 1, r));
}

// get_point uses global u
int get_point(int id, int l, int r) {
    if (l == r) return tTwo[id];
    down(id);
    int m = (l + r) >> 1;
    if (u <= m) return get_point(id << 1, l, m);
    else return get_point(id << 1 | 1, m + 1, r);
}

// build using pref_mod to avoid side effects of modifying cur inside recursion
function<void(int,int,int, const vector<int>&)> build; // forward

int init(int nn, int aarr[], int barr[]) {
    ::n = nn;
    for (int i = 0; i < n; ++i) {
        Xarr[i] = aarr[i];
        Yarr[i] = barr[i];
    }

    // init segment tree arrays (clean)
    int SZ = 4 * (n + 5);
    for (int i = 0; i < SZ; ++i) {
        t[i] = 0;
        lazy[i] = 1;
        tTwo[i] = 1;
    }
    
    long long cur = 1;


    // build function (uses prefix_mod)
    build = [&] (int id,int l,int r)
    {
        lazy[id]=1;
        tTwo[id]=1;

        if (l==r)
        {
            if (l==0) t[id]=1;
            else t[id]=Y[l-1];

            if (l) cur=mul(cur,X[l-1]);
            tTwo[id]=cur;

            return;
        }
        int m=(l+r)/2;
        build(id*2,l,m);
        build(id*2+1,m+1,r);
        t[id]=max(t[id*2],t[id*2+1]);
    };

    // build tree
    build(1, 0, n);

    // fill set se
    se.clear();
    se.insert(0);
    for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1);

    // find best: iterate as you requested: multiply cur by X[old-1] then --it then check pos=*it
    it = prev(se.end());
    int best = *it;
    // ma: pair(maxY, den) where den is cur-ref per your semantics; init with last element
    u = *it; v = n;
    pii ma = make_pair(get_range(1, 0, n), 1);

    while (it != se.begin()) {
        int old = *it;
        if (old) {
            cur = cur * 1LL * Xarr[old - 1];
            if (cur >= limit) cur = limit; // cap to avoid overflow
        }

        --it;
        int pos = *it;
        u = pos; v = n;
        int temp = get_range(1, 0, n);

        // compare ratios: ma.first/ma.second < temp/cur
        if ((long long)ma.first * cur < (long long)temp * ma.second) {
            best = pos;
            ma.first = temp;
            ma.second = 1; // follow your desired reset behavior
            cur = 1;
        }
    }

    u = best;
    int prefMod = get_point(1, 0, n);
    u = best; v = n;
    int ans = mul(prefMod, get_range(1, 0, n));
    return ans;
}

int updateX(int pos0, int val) {
    int pos = pos0 + 1;
    if (Xarr[pos - 1] != val) {
        if (Xarr[pos - 1] == 1) se.insert(pos);

        k = mul(luythua(Xarr[pos - 1], mod - 2), val); // multiplier modulo
        u = pos; v = n;
        update_range(1, 0, n);

        Xarr[pos - 1] = val;

        if (val == 1) se.erase(pos);
    }

    // find best again with same iteration logic
    it = prev(se.end());
    int best = *it;
    u = *it; v = n;
    pii ma = make_pair(get_range(1, 0, n), 1);
    long long cur = 1;

    while (it != se.begin()) {
        int old = *it;
        if (old) {
            cur = cur * 1LL * Xarr[old - 1];
            if (cur >= limit) cur = limit;
        }

        --it;
        int pos2 = *it;
        u = pos2; v = n;
        int temp = get_range(1, 0, n);

        if ((long long)ma.first * cur < (long long)temp * ma.second) {
            best = pos2;
            ma.first = temp;
            ma.second = 1;
            cur = 1;
        }
    }

    u = best;
    int prefMod = get_point(1, 0, n);
    u = best; v = n;
    return mul(prefMod, get_range(1, 0, n));
}

int updateY(int pos0, int val) {
    int pos = pos0 + 1;
    if (Yarr[pos - 1] != val) {
        u = pos; k = val;
        update_point(1, 0, n); // set t at leaf pos to val
        Yarr[pos - 1] = val;
    }

    // find best again
    it = prev(se.end());
    int best = *it;
    u = *it; v = n;
    pii ma = make_pair(get_range(1, 0, n), 1);
    long long cur = 1;

    while (it != se.begin()) {
        int old = *it;
        if (old) {
            cur = cur * 1LL * Xarr[old - 1];
            if (cur >= limit) cur = limit;
        }

        --it;
        int pos2 = *it;
        u = pos2; v = n;
        int temp = get_range(1, 0, n);

        if ((long long)ma.first * cur < (long long)temp * ma.second) {
            best = pos2;
            ma.first = temp;
            ma.second = 1;
            cur = 1;
        }
    }

    u = best;
    int prefMod = get_point(1, 0, n);
    u = best; v = n;
    return mul(prefMod, get_range(1, 0, n));
}

Compilation message (stderr)

horses.cpp: In lambda function:
horses.cpp:9:11: error: 'second' was not declared in this scope
    9 | #define Y second
      |           ^~~~~~
horses.cpp:120:24: note: in expansion of macro 'Y'
  120 |             else t[id]=Y[l-1];
      |                        ^
horses.cpp:8:11: error: 'first' was not declared in this scope
    8 | #define X first
      |           ^~~~~
horses.cpp:122:32: note: in expansion of macro 'X'
  122 |             if (l) cur=mul(cur,X[l-1]);
      |                                ^
horses.cpp:128:14: error: no match for call to '(std::function<void(int, int, int, const std::vector<int>&)>) (int, int&, int&)'
  128 |         build(id*2,l,m);
      |         ~~~~~^~~~~~~~~~
In file included from /usr/include/c++/13/functional:59,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from horses.cpp:3:
/usr/include/c++/13/bits/std_function.h:587:7: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  587 |       operator()(_ArgTypes... __args) const
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:587:7: note:   candidate expects 4 arguments, 3 provided
horses.cpp:129:14: error: no match for call to '(std::function<void(int, int, int, const std::vector<int>&)>) (int, int, int&)'
  129 |         build(id*2+1,m+1,r);
      |         ~~~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/std_function.h:587:7: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  587 |       operator()(_ArgTypes... __args) const
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:587:7: note:   candidate expects 4 arguments, 3 provided
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:131:5: error: no match for 'operator=' (operand types are 'std::function<void(int, int, int, const std::vector<int>&)>' and 'init(int, int*, int*)::<lambda(int, int, int)>')
  131 |     };
      |     ^
/usr/include/c++/13/bits/std_function.h:531:9: note: candidate: 'template<class _Functor> std::function<_Res(_ArgTypes ...)>::_Requires<std::function<_Res(_ArgTypes ...)>::_Callable<_Functor>, std::function<_Res(_ArgTypes ...)>&> std::function<_Res(_ArgTypes ...)>::operator=(_Functor&&) [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  531 |         operator=(_Functor&& __f)
      |         ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:531:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/type_traits: In substitution of 'template<bool _Cond, class _Tp> using std::__enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = std::function<void(int, int, int, const std::vector<int>&)>&]':
/usr/include/c++/13/bits/std_function.h:353:8:   required by substitution of 'template<class _Res, class ... _ArgTypes> template<class _Cond, class _Tp> using std::function<_Res(_ArgTypes ...)>::_Requires = std::__enable_if_t<_Cond::value, _Tp> [with _Cond = std::function<void(int, int, int, const std::vector<int>&)>::_Callable<init(int, int*, int*)::<lambda(int, int, int)>, init(int, int*, int*)::<lambda(int, int, int)>, std::__invoke_result<init(int, int*, int*)::<lambda(int, int, int)>&, int, int, int, const std::vector<int, std::allocator<int> >&> >; _Tp = std::function<void(int, int, int, const std::vector<int>&)>&; _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
/usr/include/c++/13/bits/std_function.h:531:2:   required by substitution of 'template<class _Functor> std::function<void(int, int, int, const std::vector<int>&)>::_Requires<std::function<void(int, int, int, const std::vector<int>&)>::_Callable<_Functor, typename std::enable_if<(! std::is_same<typename std::remove_cv<typename std::remove_reference<_Tp>::type>::type, std::function<void(int, int, int, const std::vector<int>&)> >::value), std::decay<_Ex> >::type::type, std::__invoke_result<typename std::enable_if<(! std::is_same<typename std::remove_cv<typename std::remove_reference<_Tp>::type>::type, std::function<void(int, int, int, const std::vector<int>&)> >::value), std::decay<_Ex> >::type::type&, int, int, int, const std::vector<int, std::allocator<int> >&> >, std::function<void(int, int, int, const std::vector<int>&)>&> std::function<void(int, int, int, const std::vector<int>&)>::operator=(_Functor&&) [with _Functor = init(int, int*, int*)::<lambda(int, int, int)>]'
horses.cpp:131:5:   required from here
/usr/include/c++/13/type_traits:116:11: error: no type named 'type' in 'struct std::enable_if<false, std::function<void(int, int, int, const std::vector<int>&)>&>'
  116 |     using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~~~
/usr/include/c++/13/bits/std_function.h:541:9: note: candidate: 'template<class _Functor> std::function<_Res(_ArgTypes ...)>& std::function<_Res(_ArgTypes ...)>::operator=(std::reference_wrapper<_Functor>) [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  541 |         operator=(reference_wrapper<_Functor> __f) noexcept
      |         ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:541:9: note:   template argument deduction/substitution failed:
horses.cpp:131:5: note:   'init(int, int*, int*)::<lambda(int, int, int)>' is not derived from 'std::reference_wrapper<_Tp>'
  131 |     };
      |     ^
/usr/include/c++/13/bits/std_function.h:469:7: note: candidate: 'std::function<_Res(_ArgTypes ...)>& std::function<_Res(_ArgTypes ...)>::operator=(const std::function<_Res(_ArgTypes ...)>&) [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  469 |       operator=(const function& __x)
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:469:33: note:   no known conversion for argument 1 from 'init(int, int*, int*)::<lambda(int, int, int)>' to 'const std::function<void(int, int, int, const std::vector<int>&)>&'
  469 |       operator=(const function& __x)
      |                 ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/std_function.h:487:7: note: candidate: 'std::function<_Res(_ArgTypes ...)>& std::function<_Res(_ArgTypes ...)>::operator=(std::function<_Res(_ArgTypes ...)>&&) [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  487 |       operator=(function&& __x) noexcept
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:487:28: note:   no known conversion for argument 1 from 'init(int, int*, int*)::<lambda(int, int, int)>' to 'std::function<void(int, int, int, const std::vector<int>&)>&&'
  487 |       operator=(function&& __x) noexcept
      |                 ~~~~~~~~~~~^~~
/usr/include/c++/13/bits/std_function.h:501:7: note: candidate: 'std::function<_Res(_ArgTypes ...)>& std::function<_Res(_ArgTypes ...)>::operator=(std::nullptr_t) [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}; std::nullptr_t = std::nullptr_t]'
  501 |       operator=(nullptr_t) noexcept
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:501:17: note:   no known conversion for argument 1 from 'init(int, int*, int*)::<lambda(int, int, int)>' to 'std::nullptr_t'
  501 |       operator=(nullptr_t) noexcept
      |                 ^~~~~~~~~
horses.cpp:134:10: error: no match for call to '(std::function<void(int, int, int, const std::vector<int>&)>) (int, int, int&)'
  134 |     build(1, 0, n);
      |     ~~~~~^~~~~~~~~
/usr/include/c++/13/bits/std_function.h:587:7: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int, int, int, const std::vector<int, std::allocator<int> >&}]'
  587 |       operator()(_ArgTypes... __args) const
      |       ^~~~~~~~
/usr/include/c++/13/bits/std_function.h:587:7: note:   candidate expects 4 arguments, 3 provided