[Codeforces496E] Distributing Parts

描述 Description

You are an assistant director in a new musical play. The play consists of n musical parts, each part must be performed by exactly one actor. After the casting the director chose m actors who can take part in the play. Your task is to assign the parts to actors. However, there are several limitations.

First, each actor has a certain voice range and there are some parts that he cannot sing. Formally, there are two integers for each actor, ci and di (ci ≤ di) — the pitch of the lowest and the highest note that the actor can sing. There also are two integers for each part — aj and bj (aj ≤ bj) — the pitch of the lowest and the highest notes that are present in the part. The i-th actor can perform the j-th part if and only if ci ≤ aj ≤ bj ≤ di, i.e. each note of the part is in the actor’s voice range.

According to the contract, the i-th actor can perform at most ki parts. Besides, you are allowed not to give any part to some actors (then they take part in crowd scenes).

The rehearsal starts in two hours and you need to do the assignment quickly!

输入格式 InputFormat

The first line contains a single integer n — the number of parts in the play (1 ≤ n ≤ 10⁵).

Next n lines contain two space-separated integers each, aj and bj — the range of notes for the j-th part (1 ≤ aj ≤ bj ≤ 10⁹).

The next line contains a single integer m — the number of actors (1 ≤ m ≤ 10⁵).

Next m lines contain three space-separated integers each, ci, di and ki — the range of the i-th actor and the number of parts that he can perform (1 ≤ ci ≤ di ≤ 10⁹, 1 ≤ ki ≤ 10⁹).

输出格式 OutputFormat

If there is an assignment that meets all the criteria aboce, print a single word “YES” (without the quotes) in the first line.

In the next line print n space-separated integers. The i-th integer should be the number of the actor who should perform the i-th part. If there are multiple correct assignments, print any of them.

If there is no correct assignment, print a single word “NO” (without the quotes).

样例输入 SampleInput

5
803847463 819455436
642271203 699290674
405562755 495418686
621823697 775704727
790926266 810714681
3
439900587 817601793 1
781784306 918637098 2
215450925 711629163 2

样例输出 SampleOutput

YES
2 3 3 1 2

Codeforces 496E

代码 Code

将两个数组以右端点排序，接下来考虑左端点即可。枚举演奏家把他可以演奏的歌曲扔到 set 中去，然后二分查找左端点最小的节目说明有他演奏或者他没有可以演奏的曲目。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
#define pa pair<int,int>
const int maxn=100005;
int i,j,t,n,m,l,r,k,z,y,x;
struct part
{
    int l,r,k,id;
    bool operator <(const part& tmp)const
        {
            return (r==tmp.r)?(l<tmp.l):(r<tmp.r);
        }
}a[maxn],b[maxn];
struct point
{
    int l,r,id;
    bool operator <(const point& tmp)const
        {
            return (l==tmp.l)?((r==tmp.r)?(id<tmp.id):(r<tmp.r)):(l<tmp.l);
        }
};
set <point> s;
set <point>::iterator si;
vector <pa> ans;
vector <pa>::iterator ai;
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
    scanf("%d",&m);
    for (i=1;i<=m;i++) scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].k),b[i].id=i;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    x=n;
    for (i=1,j=1;i<=m;i++)
    {
        for (;j<=n && a[j].r<=b[i].r;j++) s.insert((point){a[j].l,a[j].r,j});
        for (k=1;k<=b[i].k;k++)
        {
            si=s.lower_bound((point){b[i].l,0,0});
            if (si==s.end()) break;
            ans.push_back(make_pair(a[si->id].id,b[i].id));
            s.erase(si);
            x--;
        }
    }
    if (s.size() || x) printf("NO\n");
    else
    {
        sort(ans.begin(),ans.end());
        printf("YES\n");
        for (ai=ans.begin();ai!=ans.end();ai++) printf("%d",ai->second);
        printf("\n");
    }
    return 0;
}