求数据hack /kel
查看原帖
求数据hack /kel
317459
RyexAwl新暗车楼主2021/4/8 19:08
#include <bits/stdc++.h>

namespace wxy{

const int N = 2e6 + 5;

int c1[N],c2[N],c3[N],te[N],be[N];

int q,cnt,m;

struct node{int op,t,x,y;}task[N];


inline int rev(int idx){return (m+1-idx);}
inline int get(int x){return std::lower_bound(be+1,be+1+m,x)-be;}

inline int lowbit(int x){return x & -x;}
inline void tr_add(int c[],int x,int val){for (;x<=m;x+=lowbit(x))c[x]+=val;}
inline int tr_query(int c[],int x){
	int res = 0;
	for (;x;x-=lowbit(x)) res += c[x];
	return res;
}
inline void add1(int x,int val){tr_add(c1,x,val);}
inline void add2(int x,int val){tr_add(c2,x,val);}
inline void add3(int l,int r,int val){tr_add(c3,l,val); tr_add(c3,r+1,-val);}
inline int querye(int x){
	int res1 = tr_query(c1,x); int res2 = tr_query(c2,rev(x));
	return 2*std::min(res1,res2);
}

inline int BinarySearch(int qx){
	int x = 0,val = 0;
	for (int j = 21; j >= 0; j--){
		int delta = 1 << j;
		if (x + delta > m) continue;
		if (c2[x+delta] + val < qx){x+=delta;val+=c2[x];}
	}
	return x;
}

inline void queryans(){
	int x = 0,val = 0;
	for (int j = 21; j >= 0; j--){
		int delta = 1 << j;
		if (x + delta > m) continue;
		if (c3[x+delta] + val <= 0){x+=delta;val+=c3[x];}
	}
	if (x == 0) x++;
	if (val == 0){
		int res = querye(x);
		if (res == 0) std::cout << "Peace"<<std::endl;
		else{
			std::cout << be[x] << " " << res << std::endl;
		}
	}else{
		int y = x+1,res1=querye(x),res2=querye(y);
		if (std::max(res1,res2)==0) std::cout << "Peace"<<std::endl;
		else{
			if (res1 > res2) std::cout << be[x] << " " << res1 << std::endl;
			else {
				std::cout << be[rev(BinarySearch(res2 / 2) + 1)] << " " << res2 << std::endl;
			}
		}
	}
}

inline void main(){
	std::cin >> q; m = cnt = 0;
	for (int i = 1; i <= q; i++){
		int op; scanf("%d",&op); task[i].op = op;
		std::cin >> task[i].t;
		if (task[i].op == 2) continue;
		scanf("%d%d",&task[i].x,&task[i].y);
		te[++cnt]=task[i].x;
	}
	std::sort(te+1,te+1+cnt);
	for (int i = 1; i <= cnt; i++)
		if (i == 1 || te[i] != te[i-1]) be[++m]=te[i];
	for (int i = 1; i <= q; i++){
		if (task[i].op == 2){
			int k = task[i].t,pos = get(task[k].x);
			if (task[k].t == 0) {add1(pos,-task[k].y); add3(pos,m,-task[k].y);}
			else {add2(rev(pos),-task[k].y); add3(1,pos,task[k].y);}
			queryans();
			continue;
		}
		int pos = get(task[i].x);
		if (task[i].t == 0) {add1(pos,task[i].y); add3(pos,m,task[i].y);}
		else {add2(rev(pos),task[i].y); add3(1,pos,-task[i].y);}
		queryans();
	}
}
	
}signed main(){wxy::main(); return 0;}
2021/4/8 19:08
加载中...