51Nod——T 1631 小鲨鱼在51nod小学

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1631

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面的特长，在班里担任了许多职务。

每一个职务都有一个起始时间A和结束时间B，意为小鲨鱼在[A, B]时间内，担任了某职务(inclusively)。

现在给定小鲨鱼的职务履历表，你可以高效的给出小鲨鱼在某天担任了哪些职务吗？

p.s. 由于小鲨鱼担任的职务太多，所有任期小于一个自然月的职务都忽略不计。（如1月1日~2月1日为一个自然月，即月份加1）

p.p.s. 输入数据保证小鲨鱼同时不担任超过200种职务。（牛！）

p.p.p.s 输入的日期均为合法日期，范围在2000年01月01日~2999年12月31日。

p.p.p.p.s巨大的输入输出，推荐使用scanf/printf，编译器推荐使用Virtual C++

Input

第一行为一个整数n，代表小鲨鱼担任过N种职务。(1 <= n <= 10^5)

接下来的n行，每一行为七个整数，y0, m0, d0, y1, m1, d1, x。意为在<y0, m0, d0>到<y1, m1, d1>时间内，小鲨鱼担任了职务x。(1 <= x <= 10^9)

给定的时间皆合法，且起始日期小于或等于截止日期。职务x是唯一的。

接下来是一个整数q，代表q次查询。(1 <= q <= 10^4)

接下来的q行，每一行为三个整数<y, m, d>，代表查询的日期。时间皆合法。

Output

每一次查询输出一行结果。

首先输出一个整数n，代表此时小鲨鱼担任的职务数。（n可以为0）

接下来是n个整数，代表小鲨鱼担任的职务。职务列表保持升序。

Input示例

4

2000 01 01    2000 01 01    111

2000 01 02    2001 02 02    222

2000 01 28    2000 02 29    333

2000 01 29    2000 02 28    444

4

2000 01 01

2000 01 02

2000 01 28

2000 02 29

Output示例

0

1 222

2 222 333

2 222 333

贪心+模拟
只忽略小于一个自然月、然后。。等于的也忽略了WA半天、

 #include <algorithm>

 #include <cstdio>

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N(1e5+);

 int y0,m0,d0,y1,m1,d1,k;

 int cnt,tmp,ans[N];

 struct Work {

     int ly,lm,ld,ry,rm,rd,kind;

     Work(int ly=,int lm=,int ld=,int ry=,int rm=,int rd=,int kind=):

         ly(ly),lm(lm),ld(ld),ry(ry),rm(rm),rd(rd),kind(kind){}

     bool operator < (const Work &x)const

     {

         if(ly!=x.ly) return ly<x.ly;

         else if(lm!=x.lm) return lm<x.lm;

         else if(ld!=x.ld) return ld<x.ld;

         else if(ry!=x.ry) return ry<x.ry;

         else if(rm!=x.rm) return rm<x.rm;

         else if(rd!=x.rd) return rd<x.rd;

     }

 }job[N<<];

 inline bool check()

 {

     if(y0==y1) return (m0+==m1&&d0>d1)||m0==m1;

     else return (y0+==y1&&m0==&&m1==&&d0>d1);

 }

 inline bool if_break(Work x)

 {

     if(x.ly>y0) return ;

     else if(x.ly==y0&&x.lm>m0) return ;

     else if(x.ly==y0&&x.lm==m0&&x.ld>d0) return ;

     return ;

 }

 inline bool judge(Work x)

 {

     if(x.ry<y0) return ;

     else if(x.ry==y0)

            if(x.rm<m0) return ;

            else if(x.rm==m0)

                      if(x.rd<d0) return ;

     return ;

 }

 int Presist()

 {

     int n,q; read(n);

     for(int i=; i<=n; ++i)

     {

         read(y0),read(m0),read(d0);

         read(y1),read(m1),read(d1); read(k);

         if(!check()) job[++cnt]=Work(y0,m0,d0,y1,m1,d1,k);

     }

     std::sort(job+,job+cnt+);

     for(read(q); q--; tmp=)

     {

         read(y0),read(m0),read(d0);

         for(int i=; i<=cnt; ++i)

         {

             if(if_break(job[i])) break;

             if(judge(job[i])) ans[++tmp]=job[i].kind;

         }

         if(!tmp) puts("");

         else

         {

             printf("%d ",tmp); std::sort(ans+,ans+tmp+);

             for(int i=; i<tmp; ++i) printf("%d ",ans[i]);

             printf("%d\n",ans[tmp]);

         }

     }

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char*argv[]){;}

巴特西

51Nod——T 1631 小鲨鱼在51nod小学

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1631

最新文章

热门文章