本题 Special Judge
查看原帖
本题 Special Judge
28910
览遍千秋七海楼主2022/12/24 17:31
//Special Judge for USACO22DEC Silver Pro3
//By Expect2004
#include "testlib.h"
#include<bits/stdc++.h>
using namespace std;

int n, r[307][307];
int b[307];

#define lfc (x << 1)
#define rgc ((x << 1) | 1)
#define mid ((l + r) >> 1)

int maxval[307 * 4], minval[307 * 4];

void build(int x, int l, int r) {
	if(l == r) {
		maxval[x] = minval[x] = b[l];
		return ;
	}
	build(lfc, l, mid); build(rgc, mid + 1, r);
	maxval[x] = max(maxval[lfc], maxval[rgc]);
	minval[x] = min(minval[lfc], minval[rgc]);
}

int queryMax(int x, int l, int r, int L, int R) {
	if(L <= l && r <= R) return maxval[x];
	if(R < l || r < L) return -1000000000;
	return max(queryMax(lfc, l, mid, L, R), queryMax(rgc, mid + 1, r, L, R));
}

int queryMin(int x, int l, int r, int L, int R) {
	if(L <= l && r <= R) return minval[x];
	if(R < l || r < L) return 1000000000;
	return min(queryMin(lfc, l, mid, L, R), queryMin(rgc, mid + 1, r, L, R));
}

#undef lfc
#undef rgc
#undef mid

int main(int argc, char *argv[]) {
	registerTestlibCmd(argc, argv);
	n = inf.readInt();
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			r[i][j] = inf.readInt();
		}
	}
	for(int i = 1; i <= n; i++) {
		b[i] = ouf.readInt(-1000000000, 1000000000);
	}
	build(1, 1, n);
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			int Mx = queryMax(1, 1, n, i, j), Mn = queryMin(1, 1, n, i, j);
			int delta =  Mx - Mn;
			if(delta != r[i][j]) {
				quitf(_wa, "For range [%d, %d], Maxval is %d, Minval is %d, however, r(%d,%d)=%d", i, j, Mx, Mn, i, j, r[i][j]);
			}
		}
	}
	quitf(_ok, "Accepted");
	return 0;
}
2022/12/24 17:31
加载中...