Editorial for Khai bút đầu xuân


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 ladpro98

program sopenp;
uses    math;
type    e=record
        v,p:longint;
        end;
const   fi='';
        maxn=1 shl 20;
        maxH=2*trunc(1e6);
var     f,a:array[1..maxn] of longint;
        b:array[1..maxn] of e;
        count:array[0..maxH] of longint;
        n,l,r,i,d:longint;
        inp:text;

procedure play(bound,m:longint);
var     l,r,c,v:longint;
begin
        l:=1;c:=0;
        for r:=1 to n do
        begin
                v:=a[r];
                if count[v] = 0 then inc(c);
                inc(count[v]);
                while c>bound do
                begin
                        v:=a[l];
                        dec(count[v]);
                        if count[v]=0 then dec(c);
                        inc(l);
                end;
                f[r]:=f[r]+m*(r-l+1);
        end;
end;

procedure output;
var     i:longint;
        res:int64;
begin
        res:=0;
        for i:=1 to n do
        inc(res,int64(f[i]));
        write(res);
end;

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

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

procedure discrete;
var     i:longint;
begin
        d:=2;
        a[b[1].p]:=d;
        for i:=2 to n do
        begin
                if b[i].v<>b[i-1].v then inc(d);
                a[b[i].p]:=d;
        end;
end;


begin
        input;
        sort(1,n);
        discrete;
        play(r,1);
        fillchar(count,sizeof(count),0);
        play(l-1,-1);
        output;
end.

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1100000;
var
  new,ind,a:array[1..MAXN] of longint;
  count:array[1..MAXN] of byte;
  low,high,n:longint;
  f1,f2:text;
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,low,high);
  for i:=1 to n do
    read(f1,a[i]);
  for i:=1 to n do ind[i]:=i;
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  mid,i,j:longint;
begin
  i:=l; j:=r; mid:=a[l+random(r-l+1)];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure solve;
var
  i,j:longint;
begin
  j:=0;
  for i:=1 to n do
    if a[i]>a[i-1] then
      begin
        inc(j);
        new[ind[i]]:=j
      end
    else new[ind[i]]:=j;
end;
function cal(x:longint):longint;
var
  j,sl,i,kq:longint;
begin
  fillchar(count,sizeof(count),0);
  sl:=0; j:=1; kq:=0;
  for i:=1 to n do
    begin
      inc(count[new[i]]); if count[new[i]]=1 then inc(sl);
      while sl>x do
        begin
          if j>0 then
            begin
              dec(count[new[j]]);
              if count[new[j]]=0 then dec(sl);
            end;
          inc(j);
        end;
      kq+=i-j+1;
    end;
  exit(kq);
end;
procedure ans;
begin
  writeln(f2,cal(high)-cal(low-1));
end;
begin
  openF;
  inp;
  sort(1,n);
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111
#define modunlo 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int a[1111111],n,l,u,f[1111111];
pair<int, int> A[1111111];

long long tinh(int x){
      memset(f,0,sizeof(f));  
      if(x==0) return 0;
      int cuoi = -1;
      int so = 0;
      long long kq = 0;
      for(int i = 0;i<n;i++){
            if(so<=x && cuoi!=n)
            for(cuoi = cuoi+1;cuoi<n;cuoi++){   

                   if(f[a[cuoi]]>0)
                         f[a[cuoi]]++;
                   else{
                         so++;
                         f[a[cuoi]] = 1;
                   }
                   if(so>x) break;
            }

            kq += cuoi-i;
            f[a[i]]--;
            if(f[a[i]]==0) so--;
            //cuoi--;
      }
      return kq;
}

int main(){
      //freopen("input.in","r",stdin); 
      //freopen("output.out","w",stdout);
      scanf("%d %d %d",&n,&l,&u);
      for(int i = 0;i<n;i++){
          scanf("%d",&A[i].fi);
          A[i].se = i;
      }
      sort(A, A + n);
      a[A[0].se] = 0;
      for(int i = 1; i < n; i++){
          if(A[i].fi > A[i - 1].fi){
              a[A[i].se] = a[A[i - 1].se] + 1; 
          }
          else a[A[i].se] = a[A[i - 1].se];
      }
      long long kq1,kq2;
      kq1 = tinh(u);
     // for(int i = 0;i<n;i++) M[a[i]] = 0;
      kq2 = tinh(l-1);
      printf("%lld",kq1-kq2);
     // getch();
}

Code mẫu của ll931110

program SEQ5;
const
  input  = '';
  output = '';
  maxn = 1 shl 20;
var
  a,pos,c,x,y: array[1..maxn] of longint;
  b: array[1..maxn] of cardinal;
  n,l,u: longint;
  res: int64;

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

  readln(f, n, l, u);
  for i := 1 to n do
    begin
      readln(f, b[i]);
      pos[i] := i;
    end;

  close(f);
end;

procedure qsort(low,high: longint);
var
  i,j,x1: longint;
  p,x2: cardinal;
begin
  if low >= high then exit;
  i := low;  j := high;  p := b[random(high - low + 1) + low];

  repeat
    while b[i] < p do inc(i);
    while b[j] > p do dec(j);

    if i <= j then
      begin
        if i < j then
          begin
            x2 := b[i];  b[i] := b[j]; b[j] := x2;
            x1 := pos[i];  pos[i] := pos[j];  pos[j] := x1;
          end;

        inc(i);
        dec(j);
      end;
  until i > j;

  qsort(low,j);
  qsort(i,high);
end;

procedure construct;
var
  i,ct: longint;
begin
  ct := 1;
  a[pos[1]] := 1;
  for i := 2 to n do
    begin
      if b[i] > b[i - 1] then inc(ct);
      a[pos[i]] := ct;
    end;
end;

procedure solve;
var
  i,j,k,ct: longint;
begin
  fillchar(c, sizeof(c), 0);

  j := 1;
  ct := 1;
  c[a[1]] := 1;

  for i := 1 to n do
    begin
      while (ct < l) and (j <= n) do
        begin
          inc(j);
          if j <= n then
            begin
              if c[a[j]] = 0 then inc(ct);
              inc(c[a[j]]);
            end else break;
        end;

      x[i] := j;
      dec(c[a[i]]);
      if c[a[i]] = 0 then dec(ct);
    end;

  j := 1;
  fillchar(c, sizeof(c), 0);
  c[a[1]] := 1;
  ct := 1;

  for i := 1 to n do
    begin
      while (ct <= u) and (j <= n) do
        begin
          inc(j);
          if j <= n then
            begin
              if c[a[j]] = 0 then inc(ct);
              inc(c[a[j]]);
            end;
        end;

      if j > n then
        begin
          for k := i to n do y[k] := n;
          break;
        end;

      y[i] := j - 1;
      dec(c[a[i]]);
      if c[a[i]] = 0 then dec(ct);
    end;

  res := 0;
  for i := 1 to n do
    if x[i] <> 0 then res := res + int64(y[i] - x[i] + 1);
end;

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

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.