Submission #1499113

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<list>
#include<queue>
#include<string.h>
#include<functional>
#include<stack>
#include<deque>
#include<string>
#include<limits.h>
#include<map>
#include<set>
#include<unordered_map>
#include<cmath>
#include<unordered_set>
#define int long long
using namespace std;

int dpa[100000], dpb[100000];
vector<int>a[100000], b[100000];
signed main() {
	int x, y, q; cin >> x >> y >> q;
	for (int i = 0; i < q; i++) {
		int t, d, s; cin >> t >> d >> s; t--; s--;
		if (d) {
			b[t].push_back(s);
		}
		else {
			a[t].push_back(s);
		}
	}
	for (int i = 0; i < 100000; i++) {
		sort(a[i].begin(), a[i].end());
		if(a[i].size())a[i].push_back(1 << 29);
		int h = -5, l = -5;//始まり　直前
		for (int j = 0; j < a[i].size(); j++) {
			if (a[i][j] - 1 == l) {
				l++;
			}
			else {
				for (int o = h; o <= l; o++) {
					int MIN = 1 << 29;
					if (h != 0)MIN = min(MIN, dpa[h - 1] + o - (h - 1));
					if (l != x - 1) {
						MIN = min(MIN, dpa[l + 1] + l + 1 - o);
					}
					dpa[o] = MIN;
				}
				h = a[i][j];
				l = a[i][j];
			}
		}
	}
	for (int i = 0; i < 100000; i++) {
		sort(b[i].begin(), b[i].end());
		if(b[i].size())b[i].push_back(1 << 29);
		int h = -5, l = -5, k = -5;//始まり　直前　index
		for (int j = 0; j < b[i].size(); j++) {
			if (b[i][j] - 1 == l) {
				l++;
			}
			else {
				for (int o = h; o <= l; o++) {
					int MIN = 1 << 29;
					if (h != 0)MIN = min(MIN, dpb[h - 1] + o - (h - 1));
					if (l != y - 1) {
						MIN = min(MIN, dpb[l + 1] + l + 1 - o);
					}
					dpb[o] = MIN;
				}
				h = b[i][j];
				l = b[i][j];
				k = j;
			}
		}
	}
	int ans = *min_element(dpa, dpa + x) + *min_element(dpb, dpb + y);
	if (ans >= 1 << 29)puts("-1");
	else cout << ans << endl;
}

Submission Info

Judge Result