Codeforces

Luogu

分析

显然对于每个演奏家 $i$,我们会选满足 $c_i\leq a_j,b_j\leq d_i$ 的 $a_j$ 最小的一些乐曲。

把所有演奏家按 $d_i$ 从小到大排序,把所有乐曲按 $b_i$ 从小到大排序,然后从前往后扫,并用 set 维护所有满足 $b_j\leq d_i$ 的乐曲,每次 lower_bound 出 $a_j\geq c_i$ 的最小的 $a_j$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
struct node { int l,r,k,id; } a[N],b[N];
bool operator <(node a,node b) { return a.r<b.r; }
set<pair<int,int> > S;
int ans[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i].l=read(),a[i].r=read(),a[i].id=i;
    m=read();
    for (re int i=1;i<=m;++i)
        b[i].l=read(),b[i].r=read(),b[i].k=read(),b[i].id=i;
    sort(a+1,a+n+1),sort(b+1,b+m+1);
    for (re int i=1,p=1;i<=m;++i) {
        while (p<=n&&a[p].r<=b[i].r)
            S.insert(make_pair(a[p].l,a[p].id)),++p;
        while (b[i].k) {
            auto it=S.lower_bound(make_pair(b[i].l,0));
            if (it==S.end()) break;
            ans[it->second]=b[i].id,--b[i].k,S.erase(it);
        }
    }
    for (re int i=1;i<=n;++i)
        if (!ans[i]) { puts("NO"); return 0; }
    puts("YES");
    for (re int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}
最后修改:2019 年 11 月 10 日 03 : 22 PM