Submission #498628

#	Time	Username	Problem	Language	Result	Execution time	Memory
498628		sidon	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 KiB

elephants

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

const int MAX_N = 150'000, B = 400, NB = 500, INF = 2e9;

int N, L, X[MAX_N], num[MAX_N], pos[MAX_N], st[NB];

vector<int> a[NB], b[NB];

void recalculate(int j) {
	auto &c = a[j];

	st[j] = INF;
	if(empty(c)) return;
	st[j] = b[j][0];

	int sz = size(c), pt = sz;

	for(int i = sz; --i >= 0 ; ) {
		while(pt && X[c[i]] + L < X[c[pt-1]]) --pt;

		num[c[i]] = pt < sz ? num[c[pt]] + 1 : 1;
		pos[c[i]] = pt < sz ? pos[c[pt]] : X[c[i]] + L;
	}
}

void reset() {
	int pt = 0;

	for(auto &c : a) {
		for(int &i : c) pos[pt++] = i;
		c.clear();
	}

	for(int i = 0; i < N; i++) {
		a[i/B].push_back(pos[i]);
		b[i/B].push_back(X[pos[i]]);
	}

	for(int i = 0; i < NB; i++)
		recalculate(i);
}

void init(int n, int l, int x[]) {
	N = n, L = l;
	for(int i = 0; i < N; i++) {
		X[i] = x[i];
		a[i/B].push_back(i);
	}

	reset();
}

int l, p;

void locate(int i){
	l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
	p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
}

int update(int i, int y) {
	int redo = 0;

	locate(i);
	a[l].erase(begin(a[l]) + p);
	b[l].erase(begin(b[l]) + p);

	recalculate(l);

	if(empty(b[l]) || size(b[l]) == NB*2)
		redo = 1;

	X[i] = y;

	locate(i);
	a[l].insert(begin(a[l]) + p, i);
	b[l].insert(begin(b[l]) + p, X[i]);

	recalculate(l);

	if(redo || empty(b[l]) || size(b[l]) == NB*2)
		reset();

	int res = 0, cur = -1;

	for(int k = 0; k < NB; k++) {
		if(st[k] == INF) break;
		if(cur >= b[k].back()) continue;

		int j = upper_bound(begin(b[k]), end(b[k]), cur) - begin(b[k]);

		res += num[a[k][j]];
		cur = pos[a[k][j]];
	}

	return res;
}

Compilation message (stderr)

elephants.cpp: In function 'void locate(int)':
elephants.cpp:58:52: error: no matching function for call to 'max(long int, long long int)'
   58 |  l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
      |                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from elephants.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
elephants.cpp:58:52: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   58 |  l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
      |                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from elephants.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
elephants.cpp:58:52: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   58 |  l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
      |                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from elephants.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
elephants.cpp:58:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   58 |  l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
      |                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from elephants.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
elephants.cpp:58:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   58 |  l = max(upper_bound(st, st+NB, X[i]) - st - 1, 0LL);
      |                                                    ^