C++(g++ 7.5.0) 解法, 执行用时: 45ms, 内存消耗: 2668K, 提交时间: 2023-04-02 16:53:57

#include<bits/stdc++.h>
using namespace std;
struct Pr {
	int l{0}, r{0};
};
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> c(n + 2);
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	vector<Pr> qu(m + 5);
	for (int i = 1; i <= m; i++) {
		cin >> qu[i].l >> qu[i].r;
	}
	sort(qu.begin() + 1, qu.begin() + 1 + m, [&](const Pr& A, const Pr& B) {
		return A.l < B.l;
	});
	priority_queue<int> pq;
	vector<int> cnt(n + 2);
	int ans = 0, idx = 1;
	for (int i = 1; i <= n; i++) {
		while (idx <= m && qu[idx].l == i) {
			pq.push(qu[idx].r);
			cnt[qu[idx].r]++;
			idx++;
		}
		while (pq.size() > ans + c[i]) {
			cnt[pq.top()]--;
			pq.pop();
		}
		ans += cnt[i];
	}
	cout << ans << "\n";
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 4296K, 提交时间: 2020-04-24 14:38:54

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100100;
pair<int,int> p[MAXN];
priority_queue<int> q;
int s[MAXN],num[MAXN];
int n,m,ans,now;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(register int i=1;i<=n;i++) cin>>s[i];
    for(register int i=1;i<=m;i++) cin>>p[i].first>>p[i].second;
    sort(p+1,p+m+1);
    p[m+1].first=INT_MAX;
    for(register int i=1;i<=n;i++)
    {
        while(p[now+1].first<=i) now++,q.push(p[now].second),num[p[now].second]++;
        while(q.size()-ans>s[i]) num[q.top()]--,q.pop();
        ans+=num[i];
    }
    cout<<ans<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 53ms, 内存消耗: 2504K, 提交时间: 2020-02-26 21:23:00

#include<bits/stdc++.h>
using namespace std;
int n,m,s[110000],t,sum[110000],ans=0;
pair<int,int> a[110000];
priority_queue<int> q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&s[i]);
	for(int i=1;i<=m;i++)
	scanf("%d%d",&a[i].first,&a[i].second);
	sort(a+1,a+m+1);
	a[m+1].first=n+1;
	for(int i=1;i<=n;i++)
	{
		while(a[t+1].first<=i)
		q.push(a[++t].second),sum[a[t].second]++;
		while(q.size()>s[i]+ans) sum[q.top()]--,q.pop();
		ans+=sum[i];
	}
	printf("%d\n",ans);
}