Submission #897681


Source Code Expand

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

// Macro Tools /////////////////////////////////////////////////////////////////
#define GET_MACRO_09(A0, A1, A2, A3, A4, A5, A6, A7, A8, NAME, ...) NAME

#define EXPAND_01(MACRO, A0, ...) \
	MACRO(A0, ##__VA_ARGS__) 
#define EXPAND_02(MACRO, A0, A1, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) 
#define EXPAND_03(MACRO, A0, A1, A2, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__) 
#define EXPAND_04(MACRO, A0, A1, A2, A3, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) 
#define EXPAND_05(MACRO, A0, A1, A2, A3, A4, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) MACRO(A4, ##__VA_ARGS__) 
#define EXPAND_06(MACRO, A0, A1, A2, A3, A4, A5, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) MACRO(A4, ##__VA_ARGS__) MACRO(A5, ##__VA_ARGS__) 
#define EXPAND_07(MACRO, A0, A1, A2, A3, A4, A5, A6, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) MACRO(A4, ##__VA_ARGS__) MACRO(A5, ##__VA_ARGS__)  \
	MACRO(A6, ##__VA_ARGS__) 
#define EXPAND_08(MACRO, A0, A1, A2, A3, A4, A5, A6, A7, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) MACRO(A4, ##__VA_ARGS__) MACRO(A5, ##__VA_ARGS__)  \
	MACRO(A6, ##__VA_ARGS__) MACRO(A7, ##__VA_ARGS__) 
#define EXPAND_09(MACRO, A0, A1, A2, A3, A4, A5, A6, A7, A8, ...) \
	MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__)  \
	MACRO(A3, ##__VA_ARGS__) MACRO(A4, ##__VA_ARGS__) MACRO(A5, ##__VA_ARGS__)  \
	MACRO(A6, ##__VA_ARGS__) MACRO(A7, ##__VA_ARGS__) MACRO(A8, ##__VA_ARGS__) 

#define GET_EXPAND(...) GET_MACRO_09(__VA_ARGS__, EXPAND_09, EXPAND_08, \
	EXPAND_07, EXPAND_06, EXPAND_05, EXPAND_04, EXPAND_03, EXPAND_02, EXPAND_01)
#define EXPAND_ARG_0(MACRO, ...) GET_EXPAND(__VA_ARGS__)(MACRO, __VA_ARGS__)
#define EXPAND_ARG_1(MACRO, A0, ...) GET_EXPAND(__VA_ARGS__)(MACRO, __VA_ARGS__, A0)

#define EXPAND(MACRO, ...) EXPAND_ARG_0(MACRO, __VA_ARGS__)

#define Q(x) #x
#define QUOTE(x) Q(x)

// Input ///////////////////////////////////////////////////////////////////////
#define SCANF_INT(a) scanf("%d", &(a));
#define ID(...) int __VA_ARGS__;
#define IR(...) {EXPAND(SCANF_INT, __VA_ARGS__)}
#define I(...) ID(__VA_ARGS__) IR(__VA_ARGS__)

// #define DEFINE_INT_ARRAY(a, n) int a[n];
// #define INT_ITH_ARRAY(a, i) a[i]
// #define IAD(N, ...) EXPAND_ARG_1(DEFINE_INT_ARRAY, N, __VA_ARGS__)
// #define IAR(N, ...) REP(array_reader_i, N){ 

#define SCANF_LL(a) scanf("%lld", &(a));
#define LD(...) ll __VA_ARGS__;
#define LR(...) {EXPAND(SCANF_LL, __VA_ARGS__)}
#define L(...) LD(__VA_ARGS__) LR(__VA_ARGS__)

#define DEFINE_STR(a, n) char a[n];
#define SCANF_STR(a) scanf("%s", a);
#define SD(N, ...) EXPAND_ARG_1(DEFINE_STR, N, __VA_ARGS__)
#define SR(...) EXPAND(SCANF_STR, __VA_ARGS__)
#define S(N, ...) SD(N, __VA_ARGS__) SR(__VA_ARGS__)

// Output //////////////////////////////////////////////////////////////////////
#define LN printf("\n");

#define IP(a, ...) printf("%d", a); 

// Types ///////////////////////////////////////////////////////////////////////
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef list<int> li;
typedef list<ll> lll;
typedef map<int, int> mii;
typedef map<int, ll> mil;
typedef map<ll, int> mli;
typedef map<ll, ll> mll;

// Loop & Iteration ////////////////////////////////////////////////////////////
#define FORT(t, i, a, b) \
	for(t i = (a), loop_end_##i=(b); i < (loop_end_##i); i++)
#define FORL(i, a, b) FORT(ll, i, a, b)
#define FOR(i, a, b) FORT(int, i, a, b)
#define REPT(t, i, n) FORT(t, i, 0, n)
#define REPL(i, n) FORL(i, 0, n)
#define REP(i, n) FOR(i, 0, n)
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)

#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(a, a+n)

#define PB push_back
#define MP make_pair
#define itr iterator

// Range ///////////////////////////////////////////////////////////////////////
#define IN(x, a, b) (a<=x && x<b)
#define INC(x, a, b) (a<=x && x<=b)
int dx[8] = { 1, 0, 0,-1, 1, 1,-1,-1};
int dy[8] = { 0,-1, 1, 0,-1, 1,-1, 1};

#define LAR(a, b) ((a)=max((a), (b)))
#define SML(a, b) ((a)=min((a), (b)))

// Debug ///////////////////////////////////////////////////////////////////////
#define println(...) {printf(__VA_ARGS__); printf("\n");}
#ifdef LOCAL
#define debug(...) printf(__VA_ARGS__)
#define debugln(...) println(__VA_ARGS__)
#else
#define debug(...) {}
#define debugln(...) {}
#endif

// Numbers /////////////////////////////////////////////////////////////////////
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}

#define PRIME_MAX 1000000
bool isprime[PRIME_MAX+5];
void init_prime(){
	fill(isprime, isprime+PRIME_MAX+5, true);
	isprime[0]=isprime[1]=false;
	REP(i, PRIME_MAX+5){
		if(isprime[i]){
			for(int j=i*2; j<PRIME_MAX; j+=i){
				isprime[j]=false;
			}
		}
	}
}

vll factors(ll n){
	vll v;
	REPL(i, PRIME_MAX){
		if(!isprime[i]) continue;
		while(n%i==0){
			v.PB(i);
			n/=i;
		}
	}
	if(n>1){
		v.PB(n);
	}
	return v;
}

// BIT /////////////////////////////////////////////////////////////////////////
template<
	typename T = int
>
class bit{
public:
	T *bit_arr;
	int size;

	bit(int n){
		size = n;
		bit_arr = new T[n];
		fill(bit_arr, bit_arr+n, 0);
	}

	~bit(){
		delete bit_arr;
	}

	T sum(int a){
		T ret = 0;
		while(a){
			ret+=bit_arr[a];
			a-=a&-a;
		}
		return ret;
	}

	T sum(int a, int b){
		return sum(b)-sum(a);
	}

	T get(int a){
		return sum(a, a+1);
	}

	void add(int a, T x){
		a++;
		while(a<size){
			bit_arr[a]+=x;
			a+=a&-a;
		}
	}

	void set(int a, T x){
		add(a, get(a)-x);
	}
};
typedef bit<ll> bll;

// RMQ /////////////////////////////////////////////////////////////////////////
template<
	typename T = int,
	class Compare=less<T>
>
class rmq{
public:
	int size;
	Compare comp;
	int *dat;
	T init;
	
	rmq(int n, int init_=INT_MAX){
		init=init_;
		size = 1;
		while(size<n) size*=2;
		dat = new int[2*size-1];
		fill(dat, dat+(2*size-1), init);
	}

	~rmq(){
		delete dat;
	}

	void set(int k, T a){
		k+=size-1;
		dat[k]=a;
		while(k>0){
			k=(k-1)/2;
			dat[k]=min(dat[k*2+1], dat[k*2+2], comp);
		}
	}

	T get(int a, int b, int k, int l, int r){
		if(r<=a || b<=l) return init;
		if(a<=l && r<=b) return dat[k];
		else{
			int vl = get(a, b, k*2+1, l, (l+r)/2);
			int vr = get(a, b, k*2+2, (l+r)/2, r);
			return min(vl, vr, comp);
		}
	}

	T get(int a, int b){
		return get(a, b, 0, 0, size);
	}
};

// Others //////////////////////////////////////////////////////////////////////
#define MOD 1000000007
#define YES() printf("Yes\n")
#define NO() printf("No\n")

////////////////////////////////////////////////////////////////////////////////
#define NMAX 100000

int r, c, n;
int rs[NMAX], cs[NMAX];
ll a[NMAX];

vector<pair<pii, ll>> v;
vector<pil> grp[NMAX];
int buf[NMAX];
// bool chkd[NMAX];

#define UNDEF LLONG_MIN
bool chk(int *rr, int *cc, ll *aa, ll *dd, int nn){
	v.clear();
	REP(i, nn) grp[i].clear();
	REP(i, n){
		v.PB(MP(MP(rr[i], cc[i]), aa[i]));
	}
	SORT(v);
	REP(i, n-1){
		if(v[i].first.first!=v[i+1].first.first) continue;
		int p=v[i].first.second, q=v[i+1].first.second;
		ll d=v[i+1].second-v[i].second;
		grp[p].PB(MP(q,  d));
		grp[q].PB(MP(p, -d));
	}
	fill(dd, dd+nn, UNDEF);
	// fill(chkd, chkd+n, false);
	int bufi;
	int bufn;
	REP(i, nn){
		if(dd[i]!=UNDEF) continue;
		dd[i]=0;
		bufi=bufn=0;
		buf[bufn++]=i;
		while(bufi<bufn){
			int tp = buf[bufi++];
			for(pil p : grp[tp]){
				int tto=p.first;
				ll dif=p.second;
				if(dd[tto]==UNDEF){
					dd[tto]=dd[tp]+dif;
					buf[bufn++]=tto;
				}else{
					if(dd[tto]-dd[tp]!=dif){
						return false;
					}
				}
			}
		}
		ll mi = 0;
		REP(j, bufn){
			SML(mi, dd[buf[j]]);
		}
		REP(j, bufn){
			dd[buf[j]]-=mi;
		}
	}
	// REP(i, nn) printf("%lld ", dd[i]); LN;
	return true;
}

ll rd[NMAX], cd[NMAX];
int main(){
	IR(r, c, n);
	REP(i, n){
		IR(rs[i], cs[i]);
		rs[i]--; cs[i]--;
		LR(a[i]);
	}
	// printf("R\n");
	if(!chk(rs, cs, a, rd, c)){
		NO();
		return 0;
	}
	// printf("C\n");
	if(!chk(cs, rs, a, cd, r)){
		NO();
		return 0;
	}
	REP(i, n){
		if(a[i]-rd[cs[i]]-cd[rs[i]]<0){
			// printf("%d %d %d %lld %lld %lld\n", i, rs[i], cs[i], 
					// a[i], rd[cs[i]], cd[rs[i]]);
			NO();
			return 0;
		}
	}
	YES();
}


Submission Info

Submission Time
Task D - Grid and Integers
User pkMZ75105
Language C++14 (GCC 5.4.1)
Score 800
Code Size 9111 Byte
Status AC
Exec Time 85 ms
Memory 13424 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 #define SCANF_INT(a) scanf("%d", &(a));
                                       ^
./Main.cpp:12:2: note: in expansion of macro ‘SCANF_INT’
  MACRO(A0, ##__VA_ARGS__) MACRO(A1, ##__VA_ARGS__) MACRO(A2, ##__VA_ARGS__) 
  ^
./Main.cpp:5:69: note: in expansion of macro ‘EXPAND_03’
 #define GET_MACRO_09(A0, A1, A2, A3, A4, A5, A6, A7, A8, NAME, ...) NAME
                                                                     ^
./Main.cpp:40:28: note: in expansion of macro ‘EXPAND_ARG_0’
 #define EXPAND(MACRO, ...) EXPAND_ARG_0(MACRO, __VA_ARGS__)
                            ^
./Main.cpp:48:18: note: in expansion of macro ‘EXPAND’
 #define IR(...) {EXPAND(SCANF_INT, __VA_ARGS__)}
                  ^
./Main.cpp:331:2: note: in expansion of macro ‘IR’
  IR(r, c, n);
  ^
./Main.cpp:46:39: warning: ignoring return value of ‘int scanf(con...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 5
AC × 69
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt
Case Name Status Exec Time Memory
0_00.txt AC 5 ms 2560 KB
0_01.txt AC 5 ms 2560 KB
0_02.txt AC 5 ms 2560 KB
0_03.txt AC 5 ms 2560 KB
0_04.txt AC 5 ms 2560 KB
1_00.txt AC 7 ms 4224 KB
1_01.txt AC 7 ms 4224 KB
1_02.txt AC 7 ms 4224 KB
1_03.txt AC 7 ms 4224 KB
1_04.txt AC 7 ms 4224 KB
1_05.txt AC 6 ms 3328 KB
1_06.txt AC 56 ms 7408 KB
1_07.txt AC 61 ms 7408 KB
1_08.txt AC 70 ms 10096 KB
1_09.txt AC 69 ms 10096 KB
1_10.txt AC 79 ms 11120 KB
1_11.txt AC 61 ms 9072 KB
1_12.txt AC 85 ms 11248 KB
1_13.txt AC 63 ms 9328 KB
1_14.txt AC 84 ms 11248 KB
1_15.txt AC 83 ms 11248 KB
1_16.txt AC 83 ms 11248 KB
1_17.txt AC 82 ms 11248 KB
1_18.txt AC 81 ms 11376 KB
1_19.txt AC 82 ms 11248 KB
1_20.txt AC 53 ms 8308 KB
1_21.txt AC 23 ms 4856 KB
1_22.txt AC 8 ms 3328 KB
1_23.txt AC 47 ms 7540 KB
1_24.txt AC 65 ms 9712 KB
1_25.txt AC 50 ms 7668 KB
1_26.txt AC 9 ms 3072 KB
1_27.txt AC 12 ms 3964 KB
1_28.txt AC 82 ms 11120 KB
1_29.txt AC 26 ms 5240 KB
1_30.txt AC 77 ms 10608 KB
1_31.txt AC 30 ms 5876 KB
1_32.txt AC 68 ms 10480 KB
1_33.txt AC 75 ms 10480 KB
1_34.txt AC 13 ms 3836 KB
1_35.txt AC 78 ms 13424 KB
1_36.txt AC 15 ms 4092 KB
1_37.txt AC 34 ms 6004 KB
1_38.txt AC 57 ms 8176 KB
1_39.txt AC 19 ms 4600 KB
1_40.txt AC 55 ms 8304 KB
1_41.txt AC 26 ms 5624 KB
1_42.txt AC 57 ms 8944 KB
1_43.txt AC 49 ms 7668 KB
1_44.txt AC 75 ms 10864 KB
1_45.txt AC 21 ms 5112 KB
1_46.txt AC 75 ms 9968 KB
1_47.txt AC 30 ms 6008 KB
1_48.txt AC 25 ms 4856 KB
1_49.txt AC 11 ms 3580 KB
1_50.txt AC 44 ms 7156 KB
1_51.txt AC 57 ms 8560 KB
1_52.txt AC 10 ms 4096 KB
1_53.txt AC 14 ms 4220 KB
1_54.txt AC 25 ms 5112 KB
1_55.txt AC 37 ms 6772 KB
1_56.txt AC 38 ms 5876 KB
1_57.txt AC 62 ms 9456 KB
1_58.txt AC 66 ms 9456 KB
1_59.txt AC 9 ms 3712 KB
1_60.txt AC 5 ms 2560 KB
1_61.txt AC 5 ms 2560 KB
1_62.txt AC 5 ms 2560 KB
1_63.txt AC 5 ms 2560 KB