2018HDU多校赛 Distinct Values

题目链接

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
}op[100002];
int a[100002];
int cmp(node a,node b)
{
    if(a.l!=b.l)
        return a.l<b.l;
    else return a.r>b.r;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&op[i].l,&op[i].r);

        }
        sort(op+1,op+1+m,cmp);
        int j  = 1;
        int book[100005];
        //记录要填的每一个数出现的最后位置
        memset(book,0,sizeof book);
        int p = 1;
        for(int i=1;i<=n;i++)
        {
            while( op[j].r<i)
             //当前要填的数跳过了当前区间的右端点
            //说明当前区间已经填过了

            {
                p = 1;
                j++;
            }
            if(j>m||op[j].l>i)
            //当前要填的数要填到当前区间的右边
            //否则说明要填的位置无限制

            {
                a[i] = 1;
                book[1] = i;
            }
            else
            {
                while(book[p]>=op[j].l&&book[p]<=op[j].r)
                {
                    p++;
                }
                a[i] = p;
                book[p] = i;
            }
        }
        int top = 1;

        for(int i=1;i<=n;i++)
        {
            if(top) top=0;
            else printf(" ");
            printf("%d",a[i]);
        }
        cout<<endl;

    }
    return 0;
}
全部评论

相关推荐

迷茫的大四🐶:自信一点,我认为你可以拿到50k,低于50k完全配不上你的能力,兄弟,不要被他们骗了,你可以的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务