题解 | #清楚姐姐的学术群#

C. 考虑贪心,把所有区间丢到优先队列里。左端点小的放在最前面,左端点相同的优先右端点小的。每次从优先队列里取出一个区间,将 $xx$赋值给$a[l]a[l]$,若已经被赋值过了就直接缩小左端点,否则缩小左端点的同时将 $x-1x-1$,如果左端点大于右端点了,且数量还不能达到要求是输出-1

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct temp{
    int l,r,x,y;
};
struct node{
    int l,r,x,y;
    bool operator<(const node& b) const{
        if(l==b.l) return r<b.r;
        return l<b.l;
    }
    bool operator>(const node& b) const{
        if(l==b.l) return r>b.r;
        return l>b.l;
    }
}a[2005],b[2005];
int ans[2005];
bool cmp(node a,node b)
{
    return a.l<b.l;
}
void solve()
{
	cin>>n>>m;
    for(int i = 1;i<=n;++i)
    	ans[i] = 0;
    priority_queue<node,vector<node>,greater<node>> pq;
    for(int i = 1;i<=m;++i)
    {
        cin>>a[i].l>>a[i].r>>a[i].x>>a[i].y;
        pq.push(a[i]);
    }
    while(pq.size())
    {
        node tmp = pq.top();
        pq.pop();
        if(ans[tmp.l])
            tmp.l++;
        else
        {
            ans[tmp.l] = tmp.x;
            tmp.l++;
            tmp.y--;
        }
        if(tmp.l>tmp.r)
        {
            if(tmp.y==0)
                continue;
            cout<<"qcjjddw\n";
            return;
        }
        else if(tmp.y)
            pq.push(tmp);
    }
//     for(int i = 1;i<=m;++i)
// 	{
// 		int cnt = 0;
// 		for(int j = a[i].l;j<=a[i].r;++j)
// 			if(ans[j]==a[i].x)
// 				cnt++;
// 		if(cnt<a[i].y)
// 			assert(0);	
// 	} 
    for(int i = 1;i<=n;++i)
    {
        
        if(!ans[i])
            cout<<1<<' ';
        else
            cout<<ans[i]<<" ";
    }
}
int main()
{
//     int t;
//     cin>>t;
    int t = 1;
    while(t--)
    	solve();
    return 0;
}