Submission #289957

#	Time	Username	Problem	Language	Result	Execution time	Memory
289957		shayan_p	Holiday (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

holiday

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include"holiday.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int cost[maxn], tmp[maxn], idcost[maxn];
int A[maxn], B[maxn];
ll ANS1[2 * maxn], ANS2[2 * maxn];

struct Data{
    multiset<int> ms;
    void add(int id){
	ms.insert(-cost[id]);
    }
    void era(int id){
	ms.erase(ms.find(-cost[id]));
    }
    void clear(){
	ms.clear();
    }
    ll ask(int n){
	ll ans = 0;
	for(auto x : ms){
	    if(n == 0)
		break;
	    ans+= x;
	    n--;
	}
	return -ans;
    }    
};
Data data;

void divide(int l, int r, int L, int R, int *cst, ll *ret, int stp){
    if(l > r){
	while(L < R){
	    data.add(cst[L]);
	    L++;
	}
	return;
    }
    int mid = (l+r) >> 1;
    pli bst = {-1, -1};
    int pos = L;
    while(pos <= R && stp * pos <= mid){
	data.add(cst[pos]);
	bst = max(bst, (pli){ data.ask(mid - stp * pos), pos });
	pos++;
    }
    while(pos > L){
	--pos;
	data.era(cst[pos]);	
    }
    ret[mid] = bst.F;
    divide(l, mid-1, L, bst.S, cst, ret, stp);
    divide(mid+1, r, bst.S, R, cst, ret, stp);
}
ll solve(int n, int start, int d, int a[]){
    int n1 = start, n2 = n-n1;
    for(int i = start; i < n; i++)
	A[i-start] = a[i];
    for(int i = start-1; i >= 0; i--)
	B[start-i-1] = a[i];
    divide(0, 2 * n1 - 1, 0, n1 - 1, B, ANS1, 2);
    data.clear();
    divide(0, 2 * n2 - 1, 0, n2 - 1, A, ANS2, 1);
    data.clear();
    ll ans = ANS2[min(2 * n2-1, d)];
    for(int i = 0; i < 2 * n1 && 2 + i <= d; i++){
	ans = max(ans, ANS1[i] + ANS2[min(2 * n2 -1, d-i-2)]);
    }
    return ans;
}
ll findMaxAttraction(int n, int start, int d, int a[]){
    for(int i = 0; i < n; i++){
	cost[i] = a[i];
	a[i] = i;
	tmp[i] = i;
    }
    sort(tmp, tmp + n, [](int i, int j){ return cost[i] < cost[j]; } );
    for(int i = 0; i < n; i++){
	idcost[ tmp[i] ] = i;
    }
    
    ll ans = solve(n, start, d, a);
    reverse(a, a + n);
    ans = max(ans, solve(n, n-1-start, d, a));
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void divide(int, int, int, int, int*, ll*, int)':
holiday.cpp:51:6: error: reference to 'data' is ambiguous
   51 |      data.add(cst[L]);
      |      ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  318 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  309 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  299 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  289 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
holiday.cpp:46:6: note:                 'Data data'
   46 | Data data;
      |      ^~~~
holiday.cpp:60:2: error: reference to 'data' is ambiguous
   60 |  data.add(cst[pos]);
      |  ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  318 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  309 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  299 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  289 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
holiday.cpp:46:6: note:                 'Data data'
   46 | Data data;
      |      ^~~~
holiday.cpp:61:21: error: expected primary-expression before ')' token
   61 |  bst = max(bst, (pli){ data.ask(mid - stp * pos), pos });
      |                     ^
holiday.cpp:66:2: error: reference to 'data' is ambiguous
   66 |  data.era(cst[pos]);
      |  ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  318 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  309 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  299 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  289 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
holiday.cpp:46:6: note:                 'Data data'
   46 | Data data;
      |      ^~~~
holiday.cpp: In function 'll solve(int, int, int, int*)':
holiday.cpp:79:5: error: reference to 'data' is ambiguous
   79 |     data.clear();
      |     ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  318 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  309 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  299 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  289 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
holiday.cpp:46:6: note:                 'Data data'
   46 | Data data;
      |      ^~~~
holiday.cpp:81:5: error: reference to 'data' is ambiguous
   81 |     data.clear();
      |     ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  318 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  309 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  299 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  289 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
holiday.cpp:46:6: note:                 'Data data'
   46 | Data data;
      |      ^~~~