Submission #480094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480094	2021-10-14T14:50:10 Z	1bin	None (KOI17_shell)	C++14	Compilation error	0 ms	0 KB

shell

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1505;
ll n, k, dp[NMAX][NMAX], a[NMAX][NMAX], base = 1, ans, x, y, l, r, p;
vector<ll> seg[NMAX];
char c;

void update(int y, int idx,ll v) {
	idx += base;
	while (idx) {
		seg[y][idx] += v;
		idx /= 2;
	}
	return;
}

ll find(int y, int l, int r) {
	ll ret = dp[y][r];
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret += seg[y][l++];
		if (!(r & 1)) ret += seg[y][r--];
		l /= 2; r /= 2;
	}
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	while (base < n + 2) base *= 2;
	for (int i = 0; i <= n; i++) seg[i].resize(base * 2);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			dp[i][j] += a[i][j];
			ans += dp[i][j];
		}

	cout << ans << '\n';
	for (int t = 0; t < n; t++) {
		cin >> c >> y >> x;
		l = r = x; 
		(c == 'U') ? p = 1 : p = -1;
		a[y][x] += p;
		for (int i = y; i <= n; i++) {
			if (i != y) {
				for (; l <= r; l++) {
					ll b = find(i, 0, l);
					ll now = max(find(i, 0, l - 1), find(i - 1, 0, l)) + a[i][l];
					if (b != now) break;
				}
			}
			if (l > r) break;
			update(i, l, p);
			for (; r + 1 <= n; r++) {
				ll b = find(i, 0, r + 1) - p;
				ll now = max(find(i, 0, r), find(i - 1, 0, r + 1)) + a[i][r + 1];
				if (now == b) break;
			}
			update(i, r + 1, -p);
			//cout << "L : " << l << "   R : " << r << '\n';
			ans += p * (r - l + 1);
		}
		cout << ans << '\n';
	}
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from shell.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h: In instantiation of '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = int; _Predicate = __gnu_cxx::__ops::_Iter_equals_val<const long long int>]':
/usr/include/c++/10/bits/stl_algo.h:3902:28:   required from '_IIter std::find(_IIter, _IIter, const _Tp&) [with _IIter = int; _Tp = long long int]'
shell.cpp:58:25:   required from here
/usr/include/c++/10/bits/stl_algobase.h:1978:34: error: no matching function for call to '__iterator_category(int&)'
 1978 |          std::__iterator_category(__first));
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from shell.cpp:1:
/usr/include/c++/10/bits/stl_iterator_base_types.h:238:5: note: candidate: 'template<class _Iter> constexpr typename std::iterator_traits< <template-parameter-1-1> >::iterator_category std::__iterator_category(const _Iter&)'
  238 |     __iterator_category(const _Iter&)
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_types.h:238:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_iterator_base_types.h: In substitution of 'template<class _Iter> constexpr typename std::iterator_traits< <template-parameter-1-1> >::iterator_category std::__iterator_category(const _Iter&) [with _Iter = int]':
/usr/include/c++/10/bits/stl_algobase.h:1978:34:   required from '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = int; _Predicate = __gnu_cxx::__ops::_Iter_equals_val<const long long int>]'
/usr/include/c++/10/bits/stl_algo.h:3902:28:   required from '_IIter std::find(_IIter, _IIter, const _Tp&) [with _IIter = int; _Tp = long long int]'
shell.cpp:58:25:   required from here
/usr/include/c++/10/bits/stl_iterator_base_types.h:238:5: error: no type named 'iterator_category' in 'struct std::iterator_traits<int>'