Editorial for Xe buýt
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
uses math; const fi=''; maxn=100010; type ar=array[0..maxn] of longint; var n,xx,yy,mx:longint; a,b,c,y,d:ar; col:array[0..maxn] of int64; re:int64; procedure rf; var i:longint; begin read(xx,yy,n); for i:=1 to n do begin read(a[i],b[i],c[i]); y[i]:=b[i]; d[i]:=i; end; end; procedure sort(l,r:longint); var i,j,x,t:longint; begin i:=l; j:=r; x:=y[(i+j) shr 1]; repeat while y[i]<x do i:=i+1; while y[j]>x do j:=j-1; if i<=j then begin t:=y[i]; y[i]:=y[j]; y[j]:=t; t:=d[i]; d[i]:=d[j]; d[j]:=t; 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; procedure discr; var i:longint; begin sort(1,n); mx:=1; b[d[1]]:=1; for i:=2 to n do begin if y[i]>y[mx] then begin inc(mx); y[mx]:=y[i]; end; b[d[i]]:=mx; end; end; procedure sortt(l,r:longint); var i,j,x,y,t:longint; begin i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1]; repeat while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do i:=i+1; while (a[j]>x) or ((a[j]=x) and (b[j]>y)) do j:=j-1; if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; t:=c[i]; c[i]:=c[j]; c[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sortt(i,r); if l<j then sortt(l,j); end; procedure update(x:longint;val:int64); begin while x<=mx do begin if val<=col[x] then exit; col[x]:=val; x:=x+x and (-x); end; end; function get(x:longint):int64; var r:int64; begin r:=0; while x>0 do begin r:=max(r,col[x]); x:=x-x and (-x); end; exit(r); end; procedure pr; var i:longint; row,x:int64; begin re:=0; row:=0; i:=1; while (a[i]<1) or ((a[i]=1) and (b[i]<1)) do i:=i+1; while i<=n do begin if (i=1) or (a[i]<>a[i-1]) then row:=0; x:=get(b[i]); row:=max(row,x)+c[i]; update(b[i],row); re:=max(re,row); inc(i); end; writeln(re); end; begin assign(input,fi); reset(input); rf; discr; sortt(1,n); pr; close(input); end.
Code mẫu của ladpro98
program MBUS; uses math; const maxn=100005; fi=''; type e=record x,z,dy:longint; end; e2=record v,p:longint; end; var a:array[1..maxn] of e; col:array[0..maxn] of e2; bit:array[1..maxn] of int64; x,y,n,d:longint; res:int64; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,x,y,n); for i:=1 to n do begin readln(inp,a[i].x,col[i].v,a[i].z); col[i].p:=i; end; close(inp); end; procedure sortA(l,r:longint); var i,j:longint; p,t:e; begin if l>=r then exit; i:=l;j:=r; p:=a[random(r-l+1)+l]; repeat while (a[i].x<p.x) or ((a[i].x=p.x) and (a[i].dy<p.dy)) do inc(i); while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].dy>p.dy)) do dec(j); if i<=j then begin if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t end; inc(i);dec(j); end; until i>j; sortA(l,j);sortA(i,r); end; procedure sortCol(l,r:longint); var i,j:longint; p,t:e2; begin if l>=r then exit; i:=l;j:=r; p:=col[random(r-l+1)+l]; repeat while (col[i].v<p.v) do inc(i); while (col[j].v>p.v) do dec(j); if i<=j then begin if i<j then begin t:=col[i]; col[i]:=col[j]; col[j]:=t; end; inc(i);dec(j); end; until i>j; sortCol(l,j);sortCol(i,r); end; procedure discrete; var i:longint; begin sortCol(1,n); col[0].v:=-1; for i:=1 to n do begin if col[i].v<>col[i-1].v then inc(d); a[col[i].p].dy:=d; end; end; procedure update(i,v:longint); begin while i<=d do begin bit[i]:=max(bit[i],v); i:=i+i and (-i); end; end; function get(i:longint):longint; var t:longint; begin t:=0; while i>0 do begin t:=max(t,bit[i]); i:=i-i and (-i); end; exit(t); end; procedure dp; var i:longint; t:int64; begin sortA(1,n); for i:=1 to n do begin t:=get(a[i].dy)+a[i].z; if bit[a[i].dy]<t then update(a[i].dy,t); res:=max(res,t); end; end; begin input; discrete; dp; write(res); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <map> #define MAXN 100111 #define F first #define S second #define _(u) (u&(-u)) #define FOR(i,a,b) for(long i=a; i<=b; i++) #define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++) using namespace std; long n,X,Y,bit[MAXN],f[MAXN]; pair<pair<long,long>,long> a[MAXN]; map<long,long> m; void inp() { scanf("%ld %ld %ld",&X,&Y,&n); FOR(i,1,n) { scanf("%ld %ld %ld",&a[i].F.F,&a[i].F.S,&a[i].S); if (a[i].F.F<1 || a[i].F.S<1) a[i].S=0; } m[1]=1; m[Y]=0; FOR(i,1,n) m[a[i].F.S]=0; FORV(i,m) { typeof(i) j=i; j--; i->second=j->second+1; } FOR(i,1,n) a[i].F.S=m[a[i].F.S]; Y=m[Y]; sort(a+1,a+n+1); } long get(long u) { if (u<=0) return 0; long v=u-_(u); return max(bit[u],get(v)); } void update(long k,long u) { bit[u]=max(bit[u],k); long v=u+_(u); if (v<=n+1) update(k,v); } void solve() { long res=0; FOR(i,1,n) { f[i]=get(a[i].F.S)+a[i].S; update(f[i],a[i].F.S); res=max(res,f[i]); } printf("%ld",res); } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); inp(); solve(); return 0; }
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[] = {0, +1, 0, -1}; const int dc[] = {+1, 0, -1, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = 1e-9; const ll mod = 100000007; typedef pair<int, int> II; #define maxn 100005 #define maxe 100005 ll f[maxn]; vector<int> vx, vy; pair<II, II> P[maxn]; int X, Y, n; void update(int u, ll x){ for(int i = u; i < maxn; i += i & -i){ f[i] = max(f[i], x); } } ll get(int u){ ll res = 0; for(int i = u; i > 0; i -= i & -i){ res = max(res, f[i]); } return res; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); gi(X); gi(Y); gi(n); vx.resize(n + 2); vy.resize(n + 2); ms(f, 0); vx[0] = (X); vy[0] = (Y); vx[1] = (1); vy[1] = (1); int x, y; ll c, t; Rep(i, n){ gi(P[i].fi.fi); gi(P[i].fi.se); gi(P[i].se.fi); vx[i + 2] = (P[i].fi.fi); vy[i + 2] = (P[i].fi.se); } P[n] = mp(mp(1, 1), mp(0, 0)); P[n + 1] = mp(mp(X, Y), mp(0, 0)); sort(all(vx)); sort(all(vy)); sort(P, P + n + 2); ll res; For(i, 1, n + 1){ y = lower_bound(all(vy), P[i].fi.se) - vy.begin() + 1; t = get(y); update(y, t + P[i].se.fi); if(i == n + 1) res = t + P[i].se.fi; } cout << res; return 0; }
Code mẫu của ll931110
#include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int x[100010],y[100010],c[100010],tx[100010]; vector< pair<int,int> > a; vector< pair<int,int> > v[100010]; int n,m,k; void update(int p,int q) { while (p <= 100000) { tx[p] = max(tx[p],q); p += (p & -p); }; }; int calc(int p) { int q = 0; while (p) { q = max(q,tx[p]); p -= (p & -p); }; return q; }; int main() { // freopen("bus.in","r",stdin); // freopen("bus.ou","w",stdout); scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= k; i++) scanf("%d%d%d", &x[i], &y[i], &c[i]); for (int i = 1; i <= k; i++) a.push_back(make_pair(x[i],i)); sort(a.begin(),a.end()); x[a[0].second] = 1; int cc = 1; for (int i = 1; i < a.size(); i++) { if (a[i].first > a[i - 1].first) cc++; x[a[i].second] = cc; }; a.clear(); for (int i = 1; i <= k; i++) a.push_back(make_pair(y[i],i)); sort(a.begin(),a.end()); y[a[0].second] = 1; cc = 1; for (int i = 1; i < a.size(); i++) { if (a[i].first > a[i - 1].first) cc++; y[a[i].second] = cc; }; for (int i = 1; i <= k; i++) v[x[i]].push_back(make_pair(y[i],i)); for (int i = 1; i <= 100000; i++) sort(v[i].begin(),v[i].end()); int ret = 0; memset(tx,0,sizeof(tx)); for (int i = 1; i <= 100000; i++) for (int j = 0; j < v[i].size(); j++) { int u = v[i][j].first; int pos = v[i][j].second; // cout << i << ' ' << u << ' ' << pos << endl; int tmp = calc(u); ret = max(ret,tmp + c[pos]); update(u,tmp + c[pos]); }; printf("%d\n", ret); };
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <cstring> #include <cmath> using namespace std; #define Rep(i,n) for(int i=0;i<(n);++i) #define For(i,a,b) for(int i=(a);i<=(b);++i) #define Ford(i,a,b) for(int i=(a);i>=(b);--i) #define fi first #define se second #define pb push_back #define MP make_pair const int maxn=100010; struct Data{ int x,y,z; }; int cmp(Data a,Data b){ if(a.x==b.x)return a.y<b.y; else return a.x<b.x; } int X,Y,n,nt; int T[maxn]; Data a[maxn]; long long F[maxn]; long long B[maxn]; int main() { scanf("%d%d%d",&X,&Y,&n); Rep(i,n)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[n].x=X,a[n].y=Y,a[n].z=0; ++n; Rep(i,n)T[i]=a[i].y; sort(T,T+n); nt=unique(T,T+n)-T; sort(a,a+n,cmp); Rep(i,n){ int id=lower_bound(T,T+nt,a[i].y)-T+1; int id2=id; long long r=0; for(;id>0;id&=(id-1))r=max(r,B[id]); r+=a[i].z; F[i]=r; for(;id2<=nt;id2+=id2&(-id2))B[id2]=max(B[id2],r); } Ford(i,n-1,0)if(a[i].x==X&&a[i].y==Y){cout<<F[i]<<endl;break;} return 0; }
Comments