제출 #131488

#제출 시각아이디문제언어결과실행 시간메모리
131488MAMBA휴가 (IOI14_holiday)C++17
컴파일 에러
0 ms0 KiB
#include"holiday.h" #include <bits/stdc++.h> using namespace std; #define rep(i , j , k) for (int i = j; i < (int)k; i++) typedef long long ll; bool smax(ll &a, ll b) { if (a < b) { a = b; return true; } return false; } const int N = 1e5 + 10; int S[N], m; ll seg[N << 2], sum[N << 2]; void build(int l = 0, int r = m, int id = 1) { seg[id] = sum[id] = 0; if (l == r - 1) return; int mid = l + r >> 1; build(l , mid , id << 1); build(mid , r, id << 1 | 1); } void segAdd(int pos , int l = 0 , int r = m , int id = 1) { if (l == r - 1) { seg[id]++; sum[id] += S[l]; return; } int mid = l + r >> 1; if (pos < mid) segAdd(pos , l, mid , id << 1); else segAdd(pos , mid , r, id <<1 | 1); seg[id] = seg[id <<1] + seg[id <<1 | 1]; sum[id] = sum[id << 1] + sum[id <<1 | 1]; } ll segGet(int &rem , int l = 0, int r = m, int id = 1) { if (rem <= 0) return 0; if (rem >= seg[id]) { rem -= seg[id]; return sum[id]; } int mid = l +r >> 1; ll res = segGet(rem , mid , r ,id << 1 | 1); res += segGet(rem , l , mid , id <<1 ) ; return res; } ll ans[4][N << 2]; struct data { int l , r , s , t; data (int s_ , int t_, int l_, int r_) { s = s_; t = t_; l = l_; r = r_; } }; ll findMaxAttraction(int n, int St, int d, int A[]) { rep(i , 0 , n) S[i] = A[i]; sort(S , S + n); m = unique(S , S + n) - S; auto bfs = [&](int beg, ll res[], int cost) { build(); queue<data> q; fill(res , res + d + 1 , -1e18); q.push(data(0 , d + 1 , beg , n)); int last = beg; while (!q.empty()) { auto me = q.front(); q.pop(); int mid = me.s + me.t >> 1; if (last > me.r) { build(); last = beg; } int best = me.l; rep(i , me.l , me.r) { while (last <= i) { int id = lower_bound(S , S + m, A[last]) - S; // cout << "WTF " << id << ' ' << A[last] << ' '<< last << endl; segAdd(id); last++; } int rem = mid - (i - beg + 1) * cost; // cout << mid << " :: " << i << ' ' << rem << endl; if (smax(res[mid] , segGet(rem))) best = i; } if (mid != me.s) q.push(data(me.s , mid , me.l , best + 1)); if (mid != me.t - 1) q.push(data(mid + 1 , me.t , best , me.r)); } }; bfs(St + 1 , ans[0] , 1); bfs(St + 1 , ans[1] , 2); reverse(A , A + n); St = n - 1 - St; bfs(St + 1 , ans[2] , 1); bfs(St + 1 , ans[3] , 2); ll answer = 0; rep(i , 0 , d + 1) { smax(answer , ans[0][i] + ans[3][d - i]); smax(answer , ans[1][i] + ans[2][d - i]); if (i) { smax(answer , ans[0][i - 1] + ans[3][d - i] + A[St]); smax(answer , ans[1][i - 1] + ans[2][d - i] + A[St]); } } return answer; }

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

holiday.cpp: In function 'void build(int, int, int)':
holiday.cpp:26:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'void segAdd(int, int, int, int)':
holiday.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'll segGet(int&, int, int, int)':
holiday.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
holiday.cpp: In lambda function:
holiday.cpp:81:13: error: template argument 1 is invalid
   queue<data> q;
             ^
holiday.cpp:81:13: error: template argument 2 is invalid
holiday.cpp:83:5: error: request for member 'push' in 'q', which is of non-class type 'int'
   q.push(data(0 , d + 1 , beg , n));
     ^~~~
holiday.cpp:83:10: error: reference to 'data' is ambiguous
   q.push(data(0 , d + 1 , beg , n));
          ^~~~
holiday.cpp:63:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from holiday.cpp:2:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
holiday.cpp:86:13: error: request for member 'empty' in 'q', which is of non-class type 'int'
   while (!q.empty()) {
             ^~~~~
holiday.cpp:87:16: error: request for member 'front' in 'q', which is of non-class type 'int'
    auto me = q.front();
                ^~~~~
holiday.cpp:88:6: error: request for member 'pop' in 'q', which is of non-class type 'int'
    q.pop();
      ^~~
holiday.cpp:111:23: error: request for member 'push' in 'q', which is of non-class type 'int'
    if (mid != me.s) q.push(data(me.s , mid , me.l , best + 1));
                       ^~~~
holiday.cpp:111:28: error: reference to 'data' is ambiguous
    if (mid != me.s) q.push(data(me.s , mid , me.l , best + 1));
                            ^~~~
holiday.cpp:63:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from holiday.cpp:2:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
holiday.cpp:112:27: error: request for member 'push' in 'q', which is of non-class type 'int'
    if (mid != me.t - 1) q.push(data(mid + 1 , me.t , best , me.r));
                           ^~~~
holiday.cpp:112:32: error: reference to 'data' is ambiguous
    if (mid != me.t - 1) q.push(data(mid + 1 , me.t , best , me.r));
                                ^~~~
holiday.cpp:63:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from holiday.cpp:2:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~