1分没有,心态崩了TAT
查看原帖
1分没有,心态崩了TAT
164883
Zigh_Wang楼主2022/10/30 19:36

大佬帮我看看为啥会一分没有啊,就是简单地分类讨论

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

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INCF = 0xcfcfcfcf;

int inpt() {
	int x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-')
		f = -1, ch = getchar();
	do {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, m, q;
int A[MAXN], B[MAXN];

struct Seg {
	int mn, mx, nt0p, nt0n;
	
	Seg operator + (const Seg &qwq)const {
		Seg val;
		val.mn = min(mn, qwq.mn);
		val.mx = max(mx, qwq.mx);
		val.nt0p = min(nt0p, qwq.nt0p);
		val.nt0n = max(nt0n, qwq.nt0n);
		return val;
	}
};
struct SegmentTree {
	int l[MAXN << 2], r[MAXN << 2];
	int mn[MAXN << 2], mx[MAXN << 2], nt0p[MAXN << 2], nt0n[MAXN << 2];//nearest to 0 positive/negtive
	
	void Update(int x) {
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
		mn[x] = min(mx[x << 1], mn[x << 1 | 1]);
		nt0p[x] = min(nt0p[x << 1], nt0p[x << 1 | 1]);
		nt0n[x] = max(nt0n[x << 1], nt0n[x << 1 | 1]);
	}
	void Build(int x, int L, int R, int w[]) {
		l[x] = L, r[x] = R;
		if(L == R) {
			mx[x] = mn[x] = w[L];
			nt0p[x] = INF;
			nt0n[x] = INCF;
			if(w[L] > 0)
				nt0p[x] = w[L];
			if(w[L] < 0)
				nt0n[x] = w[L];
			return ;
		}
		int mid = L + R >> 1;
		Build(x << 1, L, mid, w);
		Build(x << 1 | 1, mid + 1, R, w);
		Update(x);
	}
	Seg Ask(int x, int L, int R) {
		if(L <= l[x] && r[x] <= R)
			return {mn[x], mx[x], nt0p[x], nt0n[x]};
		int mid = l[x] + r[x] >> 1;
		Seg val = {INF, INCF, INF, INCF};
		if(L <= mid)
			val = val + Ask(x << 1, L, R);
		if(R > mid)
			val = val + Ask(x << 1 | 1, L, R);
		return val;
	}
}segA, segB;

void Solve(Seg valA, Seg valB, int l2, int r2) {
	if(1ll * valA.nt0p * valB.mn > 1ll * valA.nt0n * valB.mx)
		printf("%lld\n", 1ll * valA.nt0p * valB.mn);
	else
		printf("%lld\n", 1ll * valA.nt0n * valB.mx);
	
//	ll resA = 0, resB = 0;
	
//	bool flag = true;
//	if(valA.nt0n == INCF)
//		resA = valA.nt0p, flag = false;
//	if(valA.nt0p == INF)
//		resA = valA.nt0n, flag = false;
//	if(flag) {
//		if(valA.nt0p * valB.mn > valA.nt0n * valB.mx)
//			resA = valA.nt0p;
//		else
//			resA = valA.nt0n;
//	}
//	
////	flag = true;
////	if(valB.nt0n == INCF)
////		resB = valB.nt0p, flag = false;
////	if(valA.nt0p == INF)
////		resB = valB.nt0n, flag = false;
////	if(flag) {
//////		if(valB.nt0p * valA.mx < valB.nt0n * valA.mn)
//////			resB = valB.nt0p;
//////		else
//////			resB = valB.nt0n;
////		if(resA * valB.mx < resA * valB.mn)
////			resB = valB.mx;
////		else
////			resB = valB.mn;
////	}
//
//	ll res = 0x3f3f3f3f3f3f3f3f;
//	for(int i = l2; i <= r2; ++i)
//		if(resA * B[i] < res)
//			res = resA * B[i], resB = B[i];
//	
//	printf("%lld\n", resA * resB);
}

int main()
{
//	freopen("game.in", "r", stdin);
//	freopen("game.out", "w", stdout);

	n = inpt(), m = inpt(), q = inpt();
	for(int i = 1; i <= n; ++i)
		A[i] = inpt();
	for(int i = 1; i <= m; ++i)
		B[i] = inpt();
	
	segA.Build(1, 1, n, A);
	segB.Build(1, 1, m, B);
	
	while(q--) {
		int l1 = inpt(), r1 = inpt();
		int l2 = inpt(), r2 = inpt();
		
		Seg valA = segA.Ask(1, l1, r1);
		Seg valB = segB.Ask(1, l2, r2);
		
		if(valA.mn < 0 && valA.mx > 0 && valB.mn < 0 && valB.mx > 0) {// A+-, B+- 
			Solve(valA, valB, l2, r2);//这一个是假的 
		}else if(valA.mn <= 0 && valA.mx >= 0 && valB.mn >= 0) {// A+-, B+
			printf("%lld\n", 1ll * valA.mx * valB.mn);
		}else if(valA.mn <= 0 && valA.mx >= 0 && valB.mx <= 0) {//A+-, B-
			printf("%lld\n", 1ll * valA.mn * valB.mx);
		}else if(valA.mn >= 0 && valB.mn <= 0 && valB.mx >= 0) {//A+, B+-
			printf("%lld\n", 1ll * valA.mn * valB.mn);
		}else if(valA.mn >= 0 && valB.mn >= 0) {//A+, B+
			printf("%lld\n", 1ll * valA.mx * valB.mn);
		}else if(valA.mn >= 0 && valB.mx <= 0) {//A+, B-
			printf("%lld\n", 1ll * valA.mn * valB.mn);
		}else if(valA.mx <= 0 && valB.mn <= 0 && valB.mx >= 0) {//A-, B+-
			printf("%lld\n", 1ll * valA.mx * valB.mx);
		}else if(valA.mx <= 0 && valB.mn >= 0) {//A-, B+
			printf("%lld\n", 1ll * valA.mx * valB.mx);
		}else {//A-, B-
			printf("%lld\n", 1ll * valA.mn * valB.mx);
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3
*/
2022/10/30 19:36
加载中...