Editorial for Hàng cây


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

const fi='';
      fo='';
      maxn=100000;
var n,re,dem:longint;
    a,b,d:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     for i:=1 to n do
     begin
          read(a[i]);
          b[i]:=i;
     end;
     close(input);
end;

procedure sort(l,r:longint);
var i,j,x,y,xx:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2]; xx:=b[(i+j) div 2];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]<xx)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (b[j]>xx)) do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function check(x:longint):boolean;
begin
     check:=(x>0) and (x<=n);
end;

procedure pr;
var cur,i:longint;
begin
     sort(1,n);
     fillchar(d,sizeof(d),0);
     dem:=0; re:=0; cur:=1;
     repeat
           inc(re);
           while d[b[cur]]=1 do inc(cur);
           d[b[cur]]:=1; inc(dem);
           for i:=0 to 1 do
               if check(b[cur]-1+2*i) and (d[b[cur]-1+2*i]=0) then
               begin
                    inc(dem); d[b[cur]-1+2*i]:=1;
               end;
           inc(cur);
     until dem=n;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 100005

bool dead[N]; int n;

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf( "%d", &n );
    priority_queue< ii, vii, greater<ii> > qu;
    fo(i,1,n) {
        int t; scanf( "%d", &t );
        qu.push(ii(t, i));
    }
    int res = 0;
    for(; !qu.empty(); qu.pop()) {
        int v = qu.top().se;
        if( dead[v] == 0 ) {
            dead[v] = dead[v-1] = dead[v+1] = 1;
            ++res;
        }
    }
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

program firs;
uses    math;
const   fi='';
        maxN=123456;
type    e=record
        v,pos:longint;
        end;
var     a:array[1..maxN] of e;
        p:array[1..maxN] of longint;
        check:array[1..maxN] of boolean;
        n,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                read(inp,a[i].v);
                a[i].pos:=i;
        end;
        close(inp);
end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
        p:e;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].v<p.v) or ((a[i].v=p.v) and (a[i].pos<p.pos)) do inc(i);
                while (a[j].v>p.v) or ((a[j].v=p.v) and (a[j].pos>p.pos)) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;

procedure init;
var     i:longint;
begin
        for i:=1 to n do
        p[a[i].pos]:=i;
end;

procedure process;
var     i:longint;
begin
        for i:=1 to n do
        if not check[i] then
        begin
                inc(res);
                check[i]:=true;
                if a[i].pos>1 then
                check[p[a[i].pos-1]]:=true;
                if a[i].pos<n then
                check[p[a[i].pos+1]]:=true;
        end;
end;

begin
        input;
        sort(1,n);
        init;
        process;
        write(res);
end.

Code mẫu của RR

//Written by RR
{$ifdef rr}
  {$r+,q+}
  {$mode objfpc}
  {$inline off}
{$else}
  {$r-,q-}
  {$mode objfpc}
  {$inline on}
{$endif}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
  snode         =       262144;

var
  f1,f2         :       text;
  n,dead        :       longint;
  nn            :       array[1..snode] of longint;
  a             :       array[1..MAXN] of longint;

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);
      for i:=1 to n do read(f1,a[i]);
    end;

procedure init(i,l,r:longint); inline;
    var
      mid,x,y:longint;
    begin
      if (l=r) then
        begin
          nn[i]:=l;
          exit;
        end;
      mid:=(l+r)>>1;
      init(i<<1,l,mid);
      init(i<<1+1,mid+1,r);
      x:=nn[i<<1]; y:=nn[i<<1+1];
      if a[x]<=a[y] then nn[i]:=x else nn[i]:=y;
    end;
procedure update(i,l,r,u:longint); inline;
    var
      mid,x,y:longint;
    begin
      if (l>r) then exit;
      if (u<l) or (r<u) then exit;
      if (u=l) and (r=u) then exit;
      mid:=(l+r)>>1;
      update(i<<1,l,mid,u);
      update(i<<1+1,mid+1,r,u);
      x:=nn[i<<1]; y:=nn[i<<1+1];
      if a[x]<=a[y] then nn[i]:=x else nn[i]:=y;
    end;

procedure solve;
    var
      time,u:longint;
    begin
      dead:=0; time:=0;
      while dead<n do
        begin
          inc(time);
          u:=nn[1];
          if (u>1) and (a[u-1]<MAXN) then
            begin
              a[u-1]:=MAXN;
              update(1,1,n,u-1);
              inc(dead);
            end;
          if (a[u]<MAXN) then
            begin
              a[u]:=MAXN;
              update(1,1,n,u);
              inc(dead);
            end;
          if (u<n) and (a[u+1]<MAXN) then
            begin
              a[u+1]:=MAXN;
              update(1,1,n,u+1);
              inc(dead);
            end;
        end;
      writeln(f2,time);
    end;


begin
  openF;
  inp;
  init(1,1,n);
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
void Quicksort(long A[],long a[],long x,long y)
{             
  long t=A[(x+y)/2];
  long i=x; long j=y;
  while(i<=j)
    {           
    while(A[i]<t) i++;
    while(A[j]>t) j--;
    if(i<=j)
      {      
      long tg=A[i];
      A[i]=A[j];
      A[j]=tg;
      long tga=a[i];
      a[i]=a[j];
      a[j]=tga;        
      i++;
      j--;
      }
    }
  if(j>x)  
  Quicksort(A,a,x,j);
  if(i<y)
  Quicksort(A,a,i,y);
} 
main()
{ 
long n,A[100002],a[100002],Free[100002],u=1,v,dem=0;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
  {
  scanf("%ld",&A[i]);
  a[i]=i; Free[i]=0;
  }
A[n+1]=0;
Quicksort(A,a,1,n);
while(u!=n&&u!=n+1)
  {
  if(A[u]!=A[u+1])
    u++;
  else  
    {        
    v=u+1;
    while(A[v]==A[v+1])
      v++;  
    Quicksort(a,Free,u,v);    
    u=v+1;
    }
  }
//printf("%ld %ld %ld ",n,a[1],Free[a[1]]);  
for(long i=1;i<=n;i++)
  if(Free[a[i]]==0)
    {
    Free[a[i]]=1;
    Free[a[i]-1]=1;
    Free[a[i]+1]=1;
    dem++;
    }
printf("%ld",dem);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program FIRS;
uses math;
const
  input  = '';
  output = '';
  maxn = 100000;
  maxv = 10000000;
type
  rec = record
    val,pos: integer;
  end;
var
  a: array[1..maxn] of integer;
  s: array[1..8 * maxn] of rec;
  n,res,u,v: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do read(f, a[i]);

  close(f);

  for i := 1 to 8 * maxn do s[i].val := maxv;
end;

procedure combine(i: integer);
begin
  s[i].val := min(s[2 * i].val,s[2 * i + 1].val);
  if s[2 * i + 1].val < s[2 * i].val then s[i].pos := s[2 * i + 1].pos
                                     else s[i].pos := s[2 * i].pos;
end;

procedure build(i,low,high: integer);
var
  mid: integer;
begin
  if low > high then exit;
  if low = high then
    begin
      s[i].val := a[low];
      s[i].pos := low;
      exit;
    end;

  mid := (low + high) div 2;
  build(2 * i,low,mid);
  build(2 * i + 1,mid + 1,high);
  combine(i);
end;

procedure update(i,low,high: integer);
var
  mid: integer;
begin
  if (v < low) or (high < u) then exit;
  if s[i].val = maxv then exit;

  if (u <= low) and (high <= v) then
    begin
      s[i].val := maxv;
      s[i].pos := 0;
      exit;
    end;

  mid := (low + high) div 2;
  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);
  combine(i);
end;

procedure solve;
var
  t: integer;
begin
  res := 0;
  repeat
    t := s[1].pos;
    if t <> 0 then
      begin
        inc(res);
        u := t - 1;
        v := t + 1;

        if t = 1 then u := 1
        else if t = n then v := n;

        update(1,1,n);
      end;
  until s[1].pos = 0;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  build(1,1,n);
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<stdio.h>
#include<queue>
#define MAX   100100
using namespace std;
typedef pair<int,int> ii;
bool b[MAX];
int n,c;
priority_queue<ii,vector<ii>,greater<ii> > q;
void init(void) {
    int i,x;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&x);
        q.push(ii(x,i));
        b[i]=true;
    }
}
void process(void) {
    c=0;
    ii x;
    int i;
    while (!q.empty()) {
        while ((!q.empty()) && (!b[q.top().second])) q.pop();
        if (!q.empty()) {
            x=q.top();
            q.pop();
            c=c+1;
            for (i=-1;i<=1;i=i+1) b[x.second+i]=false;
        }
    }
    printf("%d",c);
}
int main(void) {
    init();
    process();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define nextint __nextint()

inline int __nextint() { int x; scanf("%d", &x); return x; }

const int MAXN = 100010;

int n;
int a[MAXN];
int mm[MAXN * 4];
// bool mark[MAXN];

void init(int n, int l, int r) {
    if(l==r) {
        // cout << l << " " << a[l] << " day " << endl;
        mm[n] = a[l];
        return;
    }   
    else {
        int m = (l+r) / 2;
        init(2 *n, l,m );
        init(2*n+1,m+1,r);
        mm[n] = min(mm[n*2], mm[n*2+1]);    
    }
}

int findmin(int n, int l, int r) {
    // cout << "find min " << n << " " << l << " " << r << endl;
    if(l==r) return l;
    int m = (l+r) / 2;
    if(mm[n] == mm[2*n]) return findmin(2*n,l,m);
    else return findmin(2*n+1,m+1,r);
}

int getvalue(int n,int l, int r, int pos) {
    if(l==r) return mm[n];
    else {
        int m = (l+r)  / 2;
        if(pos <= m) return getvalue( 2 * n, l, m, pos);
        else return getvalue( 2 * n + 1, m +1, r, pos); 
    }
}

void update(int n, int l, int r, int pos, int val) {
    if(l==r) {
        mm[n] = val;
        return; 
    }
    else {
        int m = (l+r) / 2;
        if(pos <= m) update( 2 * n, l, m, pos, val);
        if(m < pos) update(2*n+1,m+1,r,pos,val);
        mm[n] = min(mm[n*2], mm[n*2+1]);
    }
}

int main() {
    scanf("%d", &n);
    Rep(i,n) scanf("%d", a+i);

    init(1,0,n-1);

    //cout << mm[1] << " " << mm[2] << " " << mm[3] << endl;

    int ngay = 0;
    while(true) {
        int pos = findmin( 1, 0, n-1);
        int value = getvalue( 1, 0, n-1, pos);
        // printf("%d %d\n", pos, value);
        if(value >= 1000000) break;
        else {
            ++ngay;
            update( 1, 0, n-1, pos, 1000000);
            if(pos > 0) update( 1, 0, n-1, pos - 1, 1000000);
            if(pos + 1 < n) update( 1, 0, n-1, pos + 1, 1000000);
        }

    }

    printf("%d\n", ngay);

    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.