답안 #500849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500849	2022-01-01T12:23:43 Z	Stickfish	Fireworks (APIO16_fireworks)	C++17	컴파일 오류	0 ms	0 KB

fireworks

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = __int128;

struct dpvl {
    ll l;
    ll r;
    ll mn; 

    dpvl() {}

    dpvl(ll l_, ll r_, ll mn_): l(l_), r(r_), mn(mn_) {}

    ll operator()(ll x) {
        if (l <= x && x <= r)
            return mn;
        return min(abs(l - x), abs(r - x)) + mn;
    }
};

const ll MAXN = 300003;
const ll INF = 1.77013e18;
vector<pair<ll, ll>> edg[MAXN];
pair<ll, ll> root[MAXN];

ll get_vl(vector<dpvl>& v, ll x) {
    ll ans = 0;
    for (auto d : v) {
        ans += d(x);
    }
    return ans;
}

ll lower_bound_dir(vector<dpvl>& v, ll x) {
    ll lb = -INF, ub = INF;
    while (ub - lb > 1) {
        ll mb = (lb + ub) / 2;
        if (get_vl(v, mb + 1) - get_vl(v, mb) < x)
            lb = mb;
        else
            ub = mb;
    }
    return ub;
}


dpvl dfs(ll v, ll n) {
    if (v >= n) {
        return {root[v].second, root[v].second, 0};
    }
    vector<dpvl> ch;
    for (auto [u, d] : edg[v]) {
        ch.push_back(dfs(u, n));
    }
    ll l = lower_bound_dir(ch, 0);
    ll r = lower_bound_dir(ch, 1);
    //assert(get_vl(ch, l) == get_vl(ch, r) && get_vl(ch, l - 1) 
    ll mn = 0;
    for (auto d : ch)
        mn += d(l);
    return {l + root[v].second, r + root[v].second, mn};
}

ll input() {
    long long x;
    cin >> x;
    return x;
}

signed main() {
    ll n = input();
    ll m = input();
    ll addans = 0;
    for (ll i = 1; i < n + m; ++i) {
        ll u = input();
        ll d = input();
        --u;
        if (u >= n) {
            addans += d;
        } else {
            edg[u].push_back({i, d});
            root[i] = {u, d};
        }
    }
    cout << (long long)(dfs(0, n).mn + addans) << endl;
}

Compilation message

fireworks.cpp: In member function 'll dpvl::operator()(ll)':
fireworks.cpp:19:29: error: call of overloaded 'abs(ll)' is ambiguous
   19 |         return min(abs(l - x), abs(r - x)) + mn;
      |                             ^
In file included from /usr/include/c++/10/cstdlib:75,
                 from /usr/include/c++/10/ext/string_conversions.h:41,
                 from /usr/include/c++/10/bits/basic_string.h:6535,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fireworks.cpp:1:
/usr/include/stdlib.h:840:12: note: candidate: 'int abs(int)'
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/10/cstdlib:77,
                 from /usr/include/c++/10/ext/string_conversions.h:41,
                 from /usr/include/c++/10/bits/basic_string.h:6535,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fireworks.cpp:1:
/usr/include/c++/10/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
fireworks.cpp:19:41: error: call of overloaded 'abs(ll)' is ambiguous
   19 |         return min(abs(l - x), abs(r - x)) + mn;
      |                                         ^
In file included from /usr/include/c++/10/cstdlib:75,
                 from /usr/include/c++/10/ext/string_conversions.h:41,
                 from /usr/include/c++/10/bits/basic_string.h:6535,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fireworks.cpp:1:
/usr/include/stdlib.h:840:12: note: candidate: 'int abs(int)'
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/10/cstdlib:77,
                 from /usr/include/c++/10/ext/string_conversions.h:41,
                 from /usr/include/c++/10/bits/basic_string.h:6535,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fireworks.cpp:1:
/usr/include/c++/10/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~