此题部分60分为什么爆零了
查看原帖
此题部分60分为什么爆零了
157585
zach0914楼主2021/4/7 16:59

期望60分,结果得0分:

/*
1. discrete the temperature
2. create 2 BITs among those discreted temperature
3. binary search the pinacle
4. compare and analyze
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define RE register
#define CLR(x, y) memset(x,y,sizeof x)
#define FOR(i, x, y) for(RE int i=x;i<=y;++i)
#define ROF(i, x, y) for(RE int i=x;i>=y;--i)
#define lowbit(x) (x&(-x))
#define DEBUG(x) cout << "$$# " << x << " #$$ "
using namespace std;

const int MAXN = 2e6 + 5, INF = 1 << 30;

typedef long long LL;

template <class T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;	
}

struct BIT
{
	int n, C[MAXN];
	inline void add(int x, int v)
	{
		while(x <= n)
		{
			C[x] += v;
			x += lowbit(x);	
		}
		return;
	}
	inline int ask(int x)
	{
		int res = 0;
		while(x)
		{
			res += C[x];
			x -= lowbit(x);
		}
		return res;
	}
} c[2];

int Q, tot = 0, table[MAXN];
int t[MAXN], op[MAXN], k[MAXN], T[MAXN], E[MAXN];

void discrete()
{
	sort(table + 1, table + tot + 1);
	tot = unique(table + 1, table + tot + 1) - (table + 1);
	return;
}
int query(int x)
{
	int L = 1, R = tot, mid;
	while(L < R)
	{
		mid = L + ((R - L) >> 1);
		if(table[mid] < x) L = mid + 1;
		else R = mid;
	}
	return L;
}

void solve()
{
	int L = 2, R = tot - 1, mid;
	// c0 < c1 的 最大温度 sum0[T] > sum1[T] 
	while(L < R)
	{
		mid = L + ((R - L) >> 1);
		if(c[0].ask(mid) <= c[1].ask(tot - mid + 1)) L = mid + 1;
		else R = mid;
	}
	int res = 0, pos = -1, can[4] = {-1, -1, -1, -1}, p[4] = {0, -1, -1, -1};
	if(R - 1 > 1) can[1] = min(c[0].ask(R - 1), c[1].ask(tot - R + 2)) << 1, p[1] = R - 1;
	can[2] = min(c[0].ask(R), c[1].ask(tot - R + 1)) << 1, p[2] = R;
	if(R + 1 < tot) can[3] = min(c[0].ask(R + 1), c[1].ask(tot - R)) << 1, p[3] = R + 1;
	FOR(i, 1, 3)
		if(can[i] >= res) res = can[i], pos = p[i];
	if(pos == -1) puts("Peace");
	else printf("%d %d\n", table[pos], res);
	return;
}

int main()
{
	scanf("%d", &Q);
	FOR(i, 1, Q)
	{
		scanf("%d", &op[i]);
		if(op[i] == 1)
		{
			scanf("%d %d %d", &t[i], &T[i], &E[i]);
			table[++ tot] = T[i];
		}
		else
		{
			scanf("%d", &k[i]);			
		}
	}
	table[++ tot] = INF, table[++ tot] = -INF, table[++ tot] = 0;
	discrete();
	c[0].n = c[1].n = tot;
	FOR(i, 1, Q)
	{
		if(op[i] == 1)
		{
			T[i] = query(T[i]);
			if(!t[i]) c[0].add(T[i], E[i]);
			else c[1].add(tot - T[i] + 1, E[i]);
		}
		else 
		{	
			if(!t[k[i]]) c[0].add(T[k[i]], -E[k[i]]);
			else c[1].add(tot - T[k[i]] + 1, -E[k[i]]);
		}
		solve();
	}
	return 0;
}
2021/4/7 16:59
加载中...