結果

問題 No.860 買い物
コンテスト
ユーザー 👑 testestest
提出日時 2018-10-24 06:49:34
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 799 ms / 1,000 ms
コード長 2,545 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 31,232 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2024-11-19 04:57:13
合計ジャッジ時間 9,171 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

//d側を1個消すとc側が1個増えるので、dの大きい方から消していく
//実質的に解説の最小全域木を求めているのと同じ（はず）
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=l;i<r;i++)
#define min(p,q)((p)<(q)?(p):(q))
#define max(p,q)((p)>(q)?(p):(q))

//seg木ここから
//↓ここを変える
//cの区間minとdのdelcntが数えられれば良い
typedef struct atai{ll c,d;}atai;
atai xx(atai x,atai y){
	atai ret;
	ret.c=min(x.c,y.c);
	ret.d=x.d+y.d;
	return ret;
}

int segNUM;
atai segN[1<<21],*seg;
void seguse(int n){segNUM=n;seg=segN+segNUM;}

//seg[]に値を与えてから初期化
void seginit(){for(int node=segNUM-1;node;node--)segN[node]=xx(segN[node*2],segN[node*2+1]);}
void segupdate(int node,atai x){
	//seg[node]をxに更新
	node+=segNUM;
	segN[node]=x;
	while(node/=2)segN[node]=xx(segN[node*2],segN[node*2+1]);
}

atai segcalcsub(int l,int r,int k,int cl,int cr){
	//完全に含むとき
	if(l<=cl&&cr<=r)return segN[k];

	int cm=(cl+cr)/2;
	//左側だけ
	if(r<=cm)return segcalcsub(l,r,2*k  ,cl,cm);
	//右側だけ
	if(cm<=l)return segcalcsub(l,r,2*k+1,cm,cr);
	//両方
	return xx(segcalcsub(l,r,2*k,cl,cm),segcalcsub(l,r,2*k+1,cm,cr));
}
atai segcalc(int l,int r){return segcalcsub(l,r,1,0,segNUM);}

int n;
int left,right;
void bs(ll i){
	//iの属する区間を求めたい
	ll ng=0,ok=i;
	while(ok-ng>1){
		ll m=(ok+ng)/2;
		if(segcalc(m,i).d==0)ok=m;
		else ng=m;
	}
	left=ng;

	ok=i,ng=n+1;
	while(ng-ok>1){
		ll m=(ok+ng)/2;
		if(segcalc(i,m).d==0)ok=m;
		else ng=m;
	}
	right=ok;
}


ll d[100010];
ll idx[100010];
int hikaku(const void*a,const void*b){
	//dの降順にindexを並べる
	if(d[*(ll*)a]>d[*(ll*)b])return -1;
	if(d[*(ll*)a]<d[*(ll*)b])return  1;
	if(*(ll*)a<*(ll*)b)return -1;
	return 1;
}

ll ans;
int main(){
	seguse(1<<17);
	scanf("%d",&n);
	rep(i,0,n){
		int a,b;
		scanf("%d%d",&a,&b);
		ans+=a+b;
		seg[i].c=a;
		seg[i].d=0;
		d[i]=b;
		idx[i]=i;
	}
	seg[0].d=1;
	seginit();
	ans+=segcalc(0,n).c-d[0];
	d[0]=0;
	
	qsort(idx,n,sizeof(ll),hikaku);	
	rep(i,0,n-1){
		//d[idx[i]]をやめる
		//idx[i]が属する区間を求めて、分割する場合と比較
		bs(idx[i]);
		//分割すると、d[idx[i]]がういて、max(min左,min右)が余分にかかる
		ll l=segcalc(left,idx[i]).c;
		ll r=segcalc(idx[i],right).c;
		if(max(l,r)<d[idx[i]]){
			//d[idx[i]]を消す
			atai temp=seg[idx[i]];
			temp.d=1;
			segupdate(idx[i],temp);
			ans+=max(l,r)-d[idx[i]];
		}
	}
	printf("%lld",ans);
}
0