期望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;
}