CSP 模拟 30

妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈

#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,m,c[N],now;
__int128 num[N],sum[N];
struct MT{int a;__int128 b;}w[N];
inline bool cmp(MT a,MT b){if(a.a==b.a)return a.b>b.b;return a.a<b.a;}
struct TREE{
	__int128 num,sum;
	int tag,cl;
}t[N<<2];
inline void update(int p){
	t[p].num=t[ls].num+t[rs].num;
	t[p].sum=t[ls].sum+t[rs].sum;
}
inline void pushdown(int p,int l,int r){
	if(t[p].cl){
		t[ls].num=t[rs].num=t[ls].sum=t[rs].sum=t[ls].tag=t[rs].tag=0;
		t[ls].cl=t[rs].cl=1;
		t[p].cl=0;
	}
	if(t[p].tag){
		int mid=l+r>>1;
		t[ls].num+=t[p].tag*(num[mid]-num[l-1]);
		t[rs].num+=t[p].tag*(num[r]-num[mid]);
		t[ls].sum+=t[p].tag*(sum[mid]-sum[l-1]);
		t[rs].sum+=t[p].tag*(sum[r]-sum[mid]);
		t[ls].tag+=t[p].tag,t[rs].tag+=t[p].tag;
		t[p].tag=0;
	}
}
inline void change(int p,int l,int r,int x){
	if(x>0){
		t[p].num+=(num[r]-num[l-1]);
		t[p].sum+=(sum[r]-sum[l-1]);
		t[p].tag+=x;
	}else{
		t[p].num=t[p].sum=t[p].tag=0;t[p].cl=1;
	}
}
inline int query(int p,int l,int r,int k){
	if(l==r){
		t[p].num-=k,t[p].sum-=w[l].a*k;
		return w[l].a*k;
	}
	pushdown(p,l,r);
	int mid=l+r>>1,res=0;
	if(k<=t[ls].num){
		res=query(ls,l,mid,k);
		update(p);return res;
	}
	res=t[ls].sum+query(rs,mid+1,r,k-t[ls].num);		
	change(ls,l,mid,-1);
	update(p);return res;
}
signed main(){
	freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),m=read();for(int i=1;i<=n;++i)c[i]=read();
	for(int i=1;i<=m;++i){
		w[i].a=read(),w[i].b=read();
		if(w[i].b==-1)w[i].b=1e12;
	}
	std::sort(w+1,w+m+1,cmp);
	for(int i=1;i<=m;++i){
		num[i]=num[i-1]+w[i].b;
		sum[i]=sum[i-1]+w[i].a*w[i].b;
		if(w[i].b==1e12){m=i;break;}
	}
	// for(int i=1;i<=m;++i)std::cout<<(ll)num[i]<<' ';std::cout<<'\n';
	// for(int i=1;i<=m;++i)std::cout<<(ll)sum[i]<<' ';std::cout<<'\n';
	int ans=0;
	for(int i=1;i<=n;++i){
		change(1,1,m,1);
		ans+=query(1,1,m,c[i]);
		// std::cout<<ans<<'\n';
		// std::cout<<(ll)t[2].num<<(ll)t[2].sum<<'\n';
	}
	std::cout<<ans<<'\n';
}