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.
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