BOSS - Ai là sếp

Tác giả: flashmt

Ngôn ngữ: C++

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 33333
using namespace std;
struct rec{int l,h,s;};
struct rec2{int d,x;};

int n,pre[maxn],f[maxn],g[maxn],p[maxn],list[maxn],re[maxn],e[1000000],ok[maxn];
rec a[maxn];
rec2 b[maxn];

bool cmp(rec i,rec j){return i.h>j.h;}
bool cmp2(rec2 i,rec2 j){return i.x>j.x;}

void add(int s)
{
    int i=s; 
    while (i<=n)
    {
        if (s>f[i]) f[i]=s;
        else break;  
        i+=i&-i;
    }     
}

int get(int i)
{
    int r=0;
    while (i)
    {
        r=max(r,f[i]);
        i-=i&-i;  
    }
    return r;
}

void visit(int x)
{
    int i; 
    re[x]=1;
    fr(i,p[x]+1,p[x+1])
    {
       visit(list[i]);
       re[x]+=re[list[i]];
    }
}

int main()
{
    int i,j,test,q;
    cin >> test;
    while (test--)
    {
       cin >> n >> q;
       fr(i,1,n+1) p[i]=f[i]=ok[i]=0;
       fr(i,1,n) 
       {
           scanf("%d%d%d",&a[i].l,&a[i].s,&a[i].h); 
           b[i].x=a[i].s;
           b[i].d=i;
       }
       sort(b+1,b+n+1,cmp2);
       fr(i,1,n) a[b[i].d].s=i;      
       sort(a+1,a+n+1,cmp);
       fr(i,1,n) g[a[i].s]=i, e[a[i].l]=i;
       fr(i,1,n)
       {
          if (!ok[i]) 
          {
             add(a[i].s);      
             ok[i]=1;
             j=i+1;
             while (j<=n && a[j].h==a[i].h) 
             {
                add(a[j].s);                
                ok[j++]=1;
             }
          }
          pre[i]=g[get(a[i].s-1)];
          p[pre[i]]++;
       }
       fr(i,2,n+1) p[i]+=p[i-1];
       fr(i,2,n) list[p[pre[i]]--]=i;
       visit(1);
       while (q--)
       {
           scanf("%d",&j);
           printf("%d %d\n",a[pre[e[j]]].l,re[e[j]]-1);  
       }
    }
    return 0;
}

Download