Hướng dẫn giải của Ai là sếp
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận