Editorial for Ai là sếp


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#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;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
{$M 1000000}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=30111;
  snode=65536;
type
  list=^node;
  node =record
          u:longint;
          next:list;
        end;
  nvien=record
          ind,sal,height:longint;
          boss,count:longint;
        end;
  ITobj=object
          nn,ind:array[1..snode] of longint;
          procedure init;
          procedure update(u,ii:longint);
          function get(u:longint):longint;
        end;
var
  f1,f2:text;
  n,q:longint;
  a:array[1..MAXN] of nvien;
  xet,ind,c:array[1..MAXN] of longint;
  ke:array[1..MAXN] of list;
  it:ITobj;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,q);
  for i:=1 to n do
    with a[i] do
      begin
        read(f1,ind,sal,height);
        count:=0; boss:=0;
      end;
end;
procedure swap(var a,b:longint); inline;
var temp:longint; begin temp:=a; a:=b; b:=temp; end;
procedure swapr(var a,b:nvien); inline;
var temp:nvien; begin temp:=a; a:=b; b:=temp; end;
var mid:longint;
procedure sort1(l,r:longint); inline;
var
  i,j:longint;
begin
  i:=l; j:=r; mid:=c[l+random(r-l+1)];
  repeat
    while c[i]<mid do inc(i);
    while c[j]>mid do dec(j);
    if i<=j then
      begin
        swap(c[i],c[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort1(i,r);
  if l<j then sort1(l,j);
end;
var key,msal,mh,mi:longint;
procedure sort2(l,r:longint);
var
  i,j:longint;
begin
  key:=l+random(r-l+1); msal:=a[key].sal; mh:=a[key].height;
  i:=l; j:=r;
  repeat
    while (a[i].height<mh) or ((a[i].height=mh) and (a[i].sal<msal)) do inc(i);
    while (a[j].height>mh) or ((a[j].height=mh) and (a[j].sal>msal)) do dec(j);
    if i<=j then
      begin
        swapr(a[i],a[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort2(i,r);
  if l<j then sort2(l,j);
end;
procedure sort3(l,r:longint);
var
  i,j:longint;
begin
  mi:=a[l+random(r-l+1)].ind; i:=l; j:=r;
  repeat
    while a[i].ind<mi do inc(i);
    while a[j].ind>mi do dec(j);
    if i<=j then
      begin
        swapr(a[i],a[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort3(i,r);
  if l<j then sort3(l,j);
end;
procedure ITobj.init;
var
  i:longint;
begin
  for i:=1 to snode do
    begin
      nn[i]:=MAXN;
      ind[i]:=0;
    end;
end;
procedure ITobj.update(u,ii:longint);
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (u<l) or (r<u) then exit;
    if (l=r) then
      begin
        nn[i]:=u;
        ind[i]:=ii;
        exit;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
    if nn[i<<1]<nn[i<<1+1] then
      begin
        nn[i]:=nn[i<<1];
        ind[i]:=ind[i<<1];
      end
    else
      begin
        nn[i]:=nn[i<<1+1];
        ind[i]:=ind[i<<1+1];
      end;
  end;
begin
  visit(1,1,n);
end;
function ITobj.get(u:longint):longint;
var
  kq,ikq:longint;
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (r<u) then exit;
    if (u<=l) then
      begin
        if nn[i]<kq then
          begin
            kq:=nn[i];
            ikq:=ind[i];
          end;
        exit;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  kq:=MAXN-1; ikq:=0;
  visit(1,1,n);
  exit(ikq);
end;
procedure add(u:longint; var a:list); inline;
var
  p:list;
begin
  new(p); p^.u:=u;
  p^.next:=a; a:=p;
end;
procedure dfs(u:longint);
var
  p:list;
  v:longint;
begin
  xet[u]:=1;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; p:=p^.next;
      if xet[v]=1 then continue;
      dfs(v);
      a[u].count+=a[v].count+1;
    end;
end;
procedure solve;
var
  i,u:longint;
begin
  //RR hoa luong
  for i:=1 to n do c[i]:=a[i].sal;
  for i:=1 to n do ind[i]:=i;
  sort1(1,n);
  for i:=1 to n do a[ind[i]].sal:=i;
  //Tim boss
  sort2(1,n);
  it.init;
  for i:=1 to n do ke[i]:=nil;
  for i:=n downto 1 do
    begin
      u:=it.get(a[i].sal);
      if u>0 then
        begin
          a[i].boss:=a[u].ind;
          add(i,ke[u]);
        end;
      it.update(a[i].sal,i);
    end;
  //Tim so nhan vien
  fillchar(xet,sizeof(xet),0);
  for i:=n downto 1 do
    if xet[i]=0 then dfs(i);
end;
function find(key:longint):longint; inline;
var
  l,r,mid,kq:longint;
begin
  l:=1; r:=n; kq:=0;
  repeat
    mid:=(l+r)>>1;
    if a[mid].ind>=key then
      begin
        kq:=mid;
        r:=mid-1;
      end
    else l:=mid+1;
  until l>r;
  exit(kq);
end;
procedure ans;
var
  u,key:longint;
begin
  sort3(1,n);
  for q:=1 to q do
    begin
      read(f1,key);
      u:=find(key);
      writeln(f2,a[u].boss,' ',a[u].count);
    end;
end;
var
  test:longint;
begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      inp;
      solve;
      ans;
    end;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 5000000;
typedef pair<int, int> II;

#define maxn 30005

Triple<int> T[maxn];
II f[maxn];
int test, n, q;

bool comp(Triple<int> const &T1, Triple<int> const &T2){
    if(T1.x != T2.x) return T1.x < T2.x;
    return T1.y < T2.y;
}

II get(int x){
    II res = mp(inf, inf);
    for(int i = x; i < maxn; i += i & -i){
        res = min(res, f[i]);
    }
    return res;
}

void update(int u, int x){
    for(int i = u; i > 0; i -= i & -i){
        f[i] = min(f[i], mp(u, x));
    }
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    gi(test);
    Rep(itest, test){
        gi(n); gi(q);
        vector<int> V;
        map<int, int> M;
        map<int, int> L;
        Rep(i, maxn) f[i] = mp(inf, inf);
        int u, v;
        II t;
        Rep(i, n) { gi(T[i].z); gi(T[i].y); gi(T[i].x); V.pb(T[i].y);}
        sort(T, T + n, comp); sort(all(V));
        for(int i = n - 1; i >= 0; i--){
            u = lower_bound(all(V), T[i].y) - V.begin() + 1;
            t = get(u + 1);
            if(t.se == inf) M[T[i].z] = 0;
            else {
                M[T[i].z] = t.se;
            }
            update(u, T[i].z);
        }
        Rep(i, n){
            int u = L[T[i].z], v = M[T[i].z];
            L[v] += u + 1;
        }
        Rep(i, q){
            gi(u);
            cout << M[u] << " " << L[u] << endl;
        }
    }
}

Code mẫu của ll931110

program BOSS;
const
  input  = '';
  output = '';
  maxn = 30000;
  maxv = 1000000;
type
  pnode = ^tnode;
  tnode = record
    val: longint;
    link: pnode;
  end;
var
  id,h,s,tmp,tmppos: array[1..maxn] of longint;
  tx,pre,nchi: array[1..maxn] of longint;
  idpos: array[1..maxv] of longint;
  a: array[1..maxn] of pnode;
  free: array[1..maxn] of boolean;
  i,nTest: longint;
  n,q: longint;
  fi,fo: text;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

procedure init;
var
  i: longint;
begin
  readln(fi, n, q);
  for i := 1 to n do readln(fi, id[i], s[i], h[i]);
end;

procedure sw(var x,y: longint);
var
  z: longint;
begin
  z := x;  x := y;  y := z;
end;

procedure swap1(i,j: longint);
begin
  sw(id[i],id[j]);  sw(h[i],h[j]);  sw(s[i],s[j]);
end;

procedure sort1(lo,hi: longint);
var
  i,j,p: longint;
begin
  if lo >= hi then exit;
  i := lo;  j := hi;  p := s[random(hi - lo + 1) + lo];

  repeat
    while s[i] < p do inc(i);
    while s[j] > p do dec(j);
    if i <= j then
      begin
        if i < j then swap1(i,j);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort1(lo,j);  sort1(i,hi);
end;

procedure swap2(i,j: longint);
begin
  sw(tmp[i],tmp[j]);  sw(tmppos[i],tmppos[j]);
end;

procedure sort2(lo,hi: longint);
var
  i,j,p: longint;
begin
  if lo >= hi then exit;
  i := lo;  j := hi;  p := tmp[random(hi - lo + 1) + lo];

  repeat
    while tmp[i] < p do inc(i);
    while tmp[j] > p do dec(j);
    if i <= j then
      begin
        if i < j then swap2(i,j);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort2(lo,j);  sort2(i,hi);
end;

//BIT operations
procedure update(x,val: longint);
begin
  while x > 0 do
    begin
      if tx[x] > val then tx[x] := val;
      x := x - (x and -x);
    end;
end;

function calc(x: longint): longint;
var
  r: longint;
begin
  r := maxv;
  while x <= maxn do
    begin
      if r > tx[x] then r := tx[x];
      x := x + (x and -x);
    end;

  calc := r;
end;

procedure add(x,y: longint);
var
  p: pnode;
begin
  new(p);
  p^.val := y;
  p^.link := a[x];
  a[x] := p;
end;

procedure DFS(u: longint);
var
  p: pnode;
begin
  free[u] := false;
  p := a[u];

  while p <> nil do
    begin
      if p^.val <> pre[u] then
        begin
          if free[p^.val] then DFS(p^.val);
          nchi[u] := nchi[u] + nchi[p^.val] + 1;
        end;

      p := p^.link;
    end;
end;

procedure precom;
var
  i,t: longint;
begin
  sort1(1,n);
  for i := 1 to n do s[i] := i;

  tmp := h;
  for i := 1 to n do tmppos[i] := i;
  sort2(1,n);

  t := 1;  h[tmppos[1]] := 1;
  for i := 2 to n do
    begin
      if tmp[i] > tmp[i - 1] then inc(t);
      h[tmppos[i]] := t;
    end;

  for i := 1 to n do idpos[id[i]] := i;

  //Find boss
  for i := 1 to n do a[i] := nil;
  for i := 1 to maxn do tx[i] := maxv;
  fillchar(pre, sizeof(pre), 0);
  fillchar(nchi, sizeof(nchi), 0);

  for i := n downto 1 do
    begin
      t := calc(h[i]);
      if t <> maxv then
        begin
          pre[i] := t;
          add(t,i);
        end;
      update(h[i],i);
    end;

  fillchar(free, sizeof(free), true);
  for i := 1 to n do if free[i] then DFS(i);
end;

procedure query;
var
  i,t: longint;
begin
  for i := 1 to q do
    begin
      readln(fi, t);
      t := idpos[t];
      if pre[t] = 0 then write(fo, 0) else write(fo, id[pre[t]]);
      writeln(fo, ' ', nchi[t]);
    end;
end;

begin
  openfile;

  readln(fi, nTest);
  for i := 1 to nTest do
    begin
      init;
      precom;
      query;
    end;

  closefile;
end.

Code mẫu của khuc_tuan

#include <iostream>
#include <set>
#include <map>
using namespace std;

int n, m;
pair<pair<int,int>, int> a[33000];
int sep[33000], solinh[33000];

struct cmp {
    bool operator()(int u, int v) {
        if(a[u].first.second != a[v].first.second) return a[u].first.second < a[v].first.second;
        else return u < v;
    }
};

int main() {
    int st;
    scanf("%d", &st);
    for(int kk=0;kk<st;++kk) {
        scanf("%d%d", &n, &m);
        for(int i=0;i<n;++i) 
            scanf("%d%d%d", &a[i].second, &a[i].first.second, &a[i].first.first);
        sort( a, a+n);
        set<int, cmp> se;
        map<int,int> ma;
        for(int i=0;i<n;++i) ma[a[i].second] = i;
        for(int i=n-1;i>=0;--i) {
            set<int, cmp> :: iterator p = se.upper_bound(i);
            if(p==se.end()) sep[i] = -1;
            else sep[i] = * p;
            se.insert(i);
        }
        memset( solinh, 0, sizeof(solinh));
        for(int i=0;i<n;++i)
            if(sep[i]!=-1) solinh[sep[i]] += solinh[i] + 1;
        for(int i=0;i<m;++i) {
            int sohieu;
            scanf("%d", &sohieu);
            int id = ma[sohieu];
            printf("%d ", sep[id]==-1 ? 0 : (a[sep[id]].second)); 
            printf("%d\n", solinh[id]);
        }
    }   
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.