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