[CSP-Sシミュレーションテスト]:C(3点+欲張り)

タイトル転送ゲート(内部問題46)
入力フォーマット
最初の行$3$整数$n,m,t$です.2行目$n$個の整数、$P_を表すi$.次の$m$行は行ごとに2つの整数で、$L_を表します.i,R_i$.
出力フォーマット
1行1つの整数が答えを表します.
サンプル
サンプル入力:
3 3 26 2 51 12 23 3
サンプル出力:
11
データ範囲とヒント
サンプルの説明:
最適な方法は、$2$次特殊ヒータ、$4$次$1$号ヒータ、$3$次$3$号ヒータを使用することである.
データ範囲:
前$20%$のデータ:$tgeqslant n$別$30%$のデータ:$P_ileqslant 30$すべてのデータ:$1leqslant n,m,tleqslant{10}^5$$1leqslant L_i,R_i\leqslant n$$1\leqslant P_i\leqslant {10}^7$
問題解
まず、バカでなければ、特殊ヒーターは最初から使っていたに違いありません.
しかし,我々の使用回数が増加するにつれて,通常のヒータで減少する費用もますます小さくなるので,これは上凸関数であるため,3分の使用回数を考慮した.
残りの欲張りだけでいい.
時間複雑度:$Theta(nlog_{1.5}(max(P_i)))$.
期待得点:$100$点.
実際の得点:$100$点.
コード時刻

#include
using namespace std;
struct rec{int L,R;}e[100001];
int n,m;
long long t;
int P[100001];
int cnt[100001];
long long ans=1LL<<60;
int h[100001],tag[100001];
long long judge(int x)
{
	for(int i=1;i<=n;i++)h[i]=max(0,P[i]-x);
	long long res=x*t;
	int flag=0;
	for(int i=1;i<=n;i++)
	{
		flag-=tag[i];
		tag[i]=0;
		h[i]=max(0,h[i]-flag);
		res+=h[i];
		flag+=h[i];
		tag[cnt[i]+1]+=h[i];
	}
	return res;
}
int main()
{
	scanf("%d%d%lld",&n,&m,&t);
	for(int i=1;i<=n;i++)cnt[i]=-1;
	for(int i=1;i<=n;i++)scanf("%d",&P[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].L,&e[i].R);
		cnt[e[i].L]=max(cnt[e[i].L],e[i].R);
	}
	int lft=0,rht=0;
	for(int i=1;i<=n;i++)
	{
		if(cnt[i-1]>=i)
		{
			rht=max(rht,cnt[i]);
			cnt[i]=rht;
		}
		if(cnt[i]==-1)lft=max(lft,P[i]);
	}
	rht=10000000;
	while(lft<=rht)
	{
		int mid=(lft+rht)>>1;
		long long flagl=judge(mid),flagr=judge(mid+1);
		if(flagl>=flagr)
		{
			lft=mid+1;
			ans=min(ans,flagr);
		}
		else
		{
			rht=mid-1;
			ans=min(ans,flagl);
		}
	}
	printf("%lld",ans);
	return 0;
}

rp++