Submission #285769

#	Time	Username	Problem	Language	Result	Execution time	Memory
285769		amoo_safar	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

#include "holiday.h"

#include <bits/stdc++.h>
#define int ll

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
const int Log = 20;
const ll Inf = 1e18;

int n, st, d, a[N], I[N], ord[N];

ll sum[N], cnt[N];
ll ans = 0;
void Add(int id, int z){
	//cerr << "!! " << id << ' ' << z << '\n';
	int pos = ord[id];
	for(; pos < N; pos += (pos & (-pos)))
		cnt[pos] += z, sum[pos] += a[id] * z;
}
ll Get(int X){
	//cerr << "## " << X << '\n';
	int res = 0;
	ll sm = 0;
	for(int l = Log - 1; l >= 0; l--){
		if(res + (1 << l) >= N) continue;
		if(cnt[res + (1 << l)] > X) continue;
		res |= (1 << l);
		X -= cnt[res];
		sm += sum[res];
	}
	return sm;
}

void Solve(int L, int R, int l, int r){
	if(L >= R) return ;
	int mid = (L + R) >> 1;


	int rm2, rem = max(0, d - (st - mid));

	int Ln = L, Rn = l;

	for(int i = Ln; i < min(mid, Rn); i++) Add(i, -1);
	Ln = mid; Rn = max(Rn, mid);

	ll val, mx = -Inf, opt = l;
	for(int i = Rn; i <= r; i++){
		if(i < mid) val = 0;
		else {
			rm2 = max(0, rem - (i - mid - 1));
			val = Get(rm2);
		}
		if(val > mx){
			mx = val;
			opt = i;
		}
		if(i != r) Add(i, 1);
	}
	Rn = r;
	ans = max(ans, mx);
	//cerr << "$$ " << mid << ' ' << mx << '\n';
	int Lrq = mid + 1, Rrq = opt;

	while(Lrq < Ln) Add(Ln - 1, 1), Ln --;
	while(Rn < Rrq) Add(Rn, 1), Rn ++;
	while(Ln < Lrq) Add(Ln, -1), Ln ++;
	while(Rrq < Rn) Add(Rn - 1, -1), Rn --;

	Solve(mid + 1, R, opt, r);
	Lrq = L, Rrq = l;


	while(Lrq < Ln) Add(Ln - 1, 1), Ln --;
	while(Rn < Rrq) Add(Rn, 1), Rn ++;
	while(Ln < Lrq) Add(Ln, -1), Ln ++;
	while(Rrq < Rn) Add(Rn - 1, -1), Rn --;
	
	Solve(L, mid, l, opt);
}

ll findMaxAttraction(int _n, int _st, int _d, int _a[]) {
    n = _n; st = _st; d = _d;
    for(int i = 0; i < n; i++) a[i] = _a[i];
    iota(I, I + n, 0);
	sort(I, I + n, [&](int i, int j){ return a[i] > a[j]; });
	for(int i = 0; i < n; i++) ord[I[i]] = i + 1;

	Solve(0, st + 1, 0, n);
	
	//cerr << "###################\n";
	reverse(a, a + n);
	st = n - 1 - st;
	iota(I, I + n, 0);
	sort(I, I + n, [&](int i, int j){ return a[i] > a[j]; });
	for(int i = 0; i < n; i++) ord[I[i]] = i + 1;
	Solve(0, st + 1, 0, n);
	
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void Solve(ll, ll, ll, ll)':
holiday.cpp:43:38: error: no matching function for call to 'max(int, ll)'
   43 |  int rm2, rem = max(0, d - (st - mid));
      |                                      ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
holiday.cpp:43:38: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   43 |  int rm2, rem = max(0, d - (st - mid));
      |                                      ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
holiday.cpp:43:38: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   43 |  int rm2, rem = max(0, d - (st - mid));
      |                                      ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
holiday.cpp:43:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |  int rm2, rem = max(0, d - (st - mid));
      |                                      ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
holiday.cpp:43:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |  int rm2, rem = max(0, d - (st - mid));
      |                                      ^
holiday.cpp:54:36: error: no matching function for call to 'max(int, ll)'
   54 |    rm2 = max(0, rem - (i - mid - 1));
      |                                    ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
holiday.cpp:54:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   54 |    rm2 = max(0, rem - (i - mid - 1));
      |                                    ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
holiday.cpp:54:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   54 |    rm2 = max(0, rem - (i - mid - 1));
      |                                    ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
holiday.cpp:54:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   54 |    rm2 = max(0, rem - (i - mid - 1));
      |                                    ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
holiday.cpp:54:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   54 |    rm2 = max(0, rem - (i - mid - 1));
      |                                    ^