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;
}
全部评论

相关推荐

后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
点赞 评论 收藏
分享
05-07 19:10
已编辑
中国科学技术大学 C++
silly01:现在先去 momenta,8-9月去鹅找日常实习,八股文算法背好了你这随便进。不过建议补充一下后端知识,MySQL、Redis看下八股,再补个6824,加点go后台的技术栈,9月随便进大厂。CPP后端只能来WXG
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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