답안 #291999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291999	2020-09-06T07:27:08 Z	Diuven	로봇 골프 (ROI19_golf)	C++17	컴파일 오류	0 ms	0 KB

golf

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

const int MOD = 998244353;

struct cells_order {
	bool operator()(pii p1, pii p2) {
		return p1.ff - p1.ss < p2.ff - p2.ss || (p1.ff - p1.ss == p2.ff - p2.ss && p1.ff + p1.ss < p2.ff + p2.ss);
	}
};

void solve() {
	int h, w, n;
	cin >> h >> w >> n;
	int m = max(h, w);
	vector<set<pii, cells_order>> intr_cells(2);
	map<pii, int> inp;
	for (int i = 0; i < n; ++i) {
		int x, y, v;
		cin >> x >> y >> v;
		--y;
		x = m - x;
		inp[{x, y}] = v;
		for (int dx = 0; dx <= 2; ++dx) {
			for (int dy = -2; dy <= 0; ++dy) {
				if (abs(dx) + abs(dy) <= 2) {
					int nx = x + dx;
					int ny = y + dy;
					if (0 <= nx && nx < m && 0 <= ny && ny < m) {
						intr_cells[(nx + ny) & 1].insert({nx, ny});
					}
				}
			}
		}
	}

	int ans = 0;
	vector<pii> change;
	for (int q = 0; q < 2; ++q) {
		// cerr << "q: " << q << endl;
		auto it = intr_cells[q].begin();
		ll sum = 0;
		map<int, int> arr;
		int prev = -INF;
		while (it != intr_cells[q].end()) {
			int i = it->ff - it->ss;
			// cerr << i << " " << prev << " " << sum << endl;
			ans = (ans + (ll) (i - prev) / 2 * (sum % MOD)) % MOD;
			int l = abs(i);
			int r = m * 2 - 2 - abs(i);

			if (i <= 0) {
				sum += arr[l];
				if (l != r)	{
					sum += arr[r];
				}
			} else if (i > 1) {
				sum -= arr[l - 2];
				sum -= arr[r + 2];
			}

			change.clear();

			while (it != intr_cells[q].end() && it->ff - it->ss == i) {
				int x, y;
				tie(x, y) = *it;
				
				if (inp.count({x, y})) {
					//arr[x + y] = inp[{x, y}];
					change.push_back({x + y, inp[{x, y}]});
				} else {
					int val1;
					if (x == 0) {
						val1 = 0;
					} else if (inp.count({x - 1, y})) {
						val1 = inp[{x - 1, y}];
					} else {
						val1 = max(arr[x + y], x + y - 2 >= 0 ? arr[x + y - 2] : 0);
					}
					int val2;
					if (y == m - 1) {
						val2 = 0;
					} else if (inp.count({x, y + 1})) {
						val2 = inp[{x, y + 1}];
					} else {
						val2 = max(arr[x + y], x + y + 2 < m * 2 ? arr[x + y + 2] : 0);
					}

					// arr[x + y] = min(val1, val2);
					change.push_back({x + y, min(val1, val2)});
					if (x + y < m - 2) {
						intr_cells[q].insert({x + y + 2, 0});
					} else if (x + y >= m + 1) {
						intr_cells[q].insert({m - 1, x + y - (m - 1) - 2});
					}
				}

				++it;
			}

			for (pii p : change) {
				if (l <= p.ff && p.ff <= r) {
					sum -= arr[p.ff];
				}

				arr[p.ff] = p.ss;

				if (l <= p.ff && p.ff <= r) {
					sum += arr[p.ff];
				}
			}


			prev = i;
			// cerr << sum << endl;
			// for (int j = l; j <= r; j += 2) {
			// 	cerr << arr[j] << " ";
			// }
			// cerr << endl;
		}

		// cerr << ((m & 1) == q ? m : m + 1) << " " << prev << " " << sum << endl;
		ans = (ans + (ll) (((m & 1) == q ? m : m + 1) - prev) / 2 * (sum % MOD)) % MOD;
	}

	cout << (ans + MOD) % MOD << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

Compilation message

In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from golf.cpp:8:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cells_order; _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<int, int> >*]':
/usr/include/c++/9/bits/stl_tree.h:2095:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cells_order; _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/9/bits/stl_tree.h:2148:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = std::pair<int, int>; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cells_order; _Alloc = std::allocator<std::pair<int, int> >]'
/usr/include/c++/9/bits/stl_set.h:520:48:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<int, int>; _Compare = cells_order; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
golf.cpp:54:48:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~