Submission #1607329

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<map>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

typedef long long ll;
typedef pair<int, ll> P;

int r, c;
int n;
vector<P> G[105000];

int main()
{
	cin >> r >> c;
	cin >> n;
	int ri, ci, ai;
	for (int i = 0; i < n; i++) {
		cin >> ri >> ci >> ai;
		ri--; ci--;
		G[ri].push_back(P(ci, ai));
	}
	for (int i = 0; i < r; i++) {
		sort(G[i].begin(), G[i].end());
	}

	int ope = 0;
	int i = 0;
	while (i < r - 1) {
		int j = 0, k = 0;
		int lu = -1;
		int ld = -1;
		while (j < G[i].size() || k < G[i + 1].size()) {

			int s, t;
			if(j!=G[i].size()) s = G[i][j].first;
			else s = INF;
			if(k!=G[i+1].size()) t = G[i + 1][k].first;
			else t = INF;

			if (s < t) {
				if (lu != -1 && ld != -1) {
					ll rans = G[i][lu].second;
					ll lans = G[i][j].second + G[i + 1][ld].second;
					if (rans > lans) {
						ope = 1; break;
					}
				}
				j++;
			}
			if (s > t) {
				if (lu != -1 && ld != -1) {
					ll rans = G[i][lu].second + G[i + 1][k].second;
					ll lans = G[i + 1][ld].second;
					if (rans < lans) {
						ope = 1; break;
					}
				}
				k++;
			}
			if (s == t) {
				int l = j; int m = k;
				if (lu != -1 && ld!=-1) {
					ll rans = G[i][lu].second + G[i + 1][k].second;
					ll lans = G[i + 1][ld].second + G[i][j].second;

					//printf("s:%d,t:%d,rans:%lld,lans:%lld\n", s, t, rans, lans);
					if (rans != lans) {
						ope = 1; break;
					}
					else {
						lu = j; ld=k;
						j++; k++;
					}
				}
				else {
					int ru = G[i][j].second;
					int rd = G[i + 1][k].second;
					if (j > 0) {
						for (int l = j -1; l >= 0; l--) {
							ll rans = G[i][l].second + rd;
							if (rans < ru) {
								ope = 1; break;
							}
						} 
					}
					if (k > 0) {
						for (int l = k - 1; l >= 0; l--) {
							ll lans = G[i+1][l].second + ru;
							if (lans < rd) {
								ope = 1; break;
							}
						}
					}
					if (ope == 1)break;
					lu = j; ld = k;
					j++; k++;
				}
			}
		}
		if (ope == 1)break;
		i++;
	}
	if (ope == 1)cout << "No" << endl;
	else cout << "Yes" << endl;

	return 0;
}

Submission Info

Judge Result