Hướng dẫn giải của Con Voi
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
uses math; const fi=''; maxn=300000; z=1000000007; var n,maxc,re:longint; a,b,f,g,d:array[1..maxn] of longint; procedure sort(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; 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 sortt(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=b[(i+j) shr 1]; repeat while b[i]<x do i:=i+1; while b[j]>x do j:=j-1; if i<=j then begin y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=d[i]; d[i]:=d[j]; d[j]:=y; 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 edit; var i:longint; begin maxc:=1; a[d[1]]:=1; for i:=2 to n do begin if b[i]>b[maxc] then begin maxc:=maxc+1; b[maxc]:=b[i]; end; a[d[i]]:=maxc; end; end; procedure rf; var i:longint; begin read(n); for i:=1 to n do begin read(a[i],b[i]); d[i]:=i; end; sort(1,n); sortt(1,n); edit; end; function calc(x:longint;var num:longint):longint; var r:longint; begin num:=0; r:=0; while x>0 do begin if f[x]=r then begin num:=num+g[x]; if num>=z then num:=num-z; end; if f[x]>r then begin r:=f[x]; num:=g[x]; end; x:=x-x and (-x); end; calc:=r; end; procedure add(x,val,num:longint); begin while x<=maxc do begin if val<f[x] then exit; if val=f[x] then begin g[x]:=g[x]+num; if g[x]>=z then g[x]:=g[x]-z; end else begin f[x]:=val; g[x]:=num; end; x:=x+x and (-x); end; end; procedure pr; var i,x,val,num:longint; begin for i:=1 to n do begin x:=a[i]; val:=calc(x-1,num); if num=0 then num:=1; add(x,val+1,num); end; val:=calc(maxc,num); writeln(val); writeln(num); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000010 #define MOD 1000000007 #define N vii P; //point vi last, cnt; //cnt[i] = so cach nhay do dai i vvii L; int n; void update( int i, int y, int add ) { cnt[i] = (cnt[i] + add) % MOD; L[i].pb(ii(y, (L[i].back().se + add) % MOD)); last[i] = y; } void enter() { scanf("%d",&n); rep(i,n) { int x, y; scanf("%d%d",&x,&y); P.pb(ii(x,y)); } } bool cmp(const ii &a, const ii &b) { return a.fi < b.fi || a.fi == b.fi && a.se > b.se; } void solve() { sort(all(P),cmp); L.resize(n+1); last.resize(n+1); cnt.resize(n+1); fill(all(last), INF); tr(L, it) it->pb(ii(INF, 0)); update(0, -INF, 1); int best = 0; tr(P, it) { int A = lower_bound(all(last), it->se) - last.begin() - 1; /*typeof(L[0].rend()) B = lower_bound(rall(L[A]), ii(it->se, -INF)); update(A+1, it->se, (cnt[A] - B->se) % MOD);*/ update(A+1, it->se, (cnt[A] - lower_bound(rall(L[A]), ii(it->se, -INF))->se) % MOD); best = max(best, A+1); } printf("%d\n%d\n", best, (L[best].back().se + MOD) % MOD); } int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif enter(); solve(); return 0; }
Code mẫu của RR
//Written by RR {$MODE OBJFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 300111; base = 1000000007; var f1,f2 : text; n,d : longint; x,y,f,reg : array[0..MAXN] of longint; last,sl,ind : array[1..MAXN] of longint; 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); for i:=1 to n do read(f1,x[i],y[i]); end; procedure swap(var a,b:longint); inline; var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure sort(l,r:longint); inline; var i,j,mx,my,key:longint; begin i:=l; j:=r; key:=l+random(r-l+1); mx:=x[key]; my:=y[key]; repeat while (y[i]<my) or ((y[i]=my) and (x[i]>mx)) do inc(i); while (y[j]>my) or ((y[j]=my) and (x[j]<mx)) do dec(j); if i<=j then begin swap(x[i],x[j]); swap(y[i],y[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function find(key:longint):longint; inline; var res,l,r,mid:longint; begin res:=0; l:=1; r:=d; while (l<=r) do begin mid:=(l+r)>>1; if last[mid]<key then begin res:=mid; l:=mid+1; end else r:=mid-1; end; exit(res); end; function find1(l,r,key:longint):longint; inline; var mid,res:longint; begin res:=r; while (l<=r) do begin mid:=(l+r)>>1; if last[mid]<key then begin res:=mid; r:=mid-1; end else l:=mid+1; end; exit(res); end; function find2(l,r,key:longint):longint; inline; var mid,res:longint; begin res:=l; while (l<=r) do begin mid:=(l+r)>>1; if ind[mid]<key then begin res:=mid; l:=mid+1; end else r:=mid-1; end; exit(res); end; procedure solve; var i,k,u,v:longint; begin //Tinh do dai day con tang dai nhat d:=0; for i:=1 to n do begin k:=find(x[i]); f[i]:=k+1; d:=max(d,k+1); last[k+1]:=x[i]; inc(sl[k+1]); end; writeln(f2,d); //Dem phan phoi for i:=2 to d do sl[i]:=sl[i-1]+sl[i]; for i:=n downto 1 do begin last[sl[f[i]]]:=x[i]; ind[sl[f[i]]]:=i; reg[sl[f[i]]]:=f[i]; dec(sl[f[i]]); end; //Dem so luong fillchar(f,sizeof(f),0); f[1]:=1; for i:=2 to n do if reg[i]=1 then f[i]:=f[i-1]+1 else begin u:=find1(sl[reg[i]-1]+1,sl[reg[i]],last[i]); v:=find2(sl[reg[i]-1]+1,sl[reg[i]],ind[i]); if reg[u-1]+2=reg[i] then f[u-1]:=0; if u>v then f[i]:=1 else f[i]:=f[v]-f[u-1]; if f[i]<0 then inc(f[i],base); if (i<>sl[reg[i]]+1) then begin f[i]:=(f[i-1]+f[i]); if f[i]>base then dec(f[i],base); end; end; writeln(f2,f[n]); end; begin openF; inp; sort(1,n); solve; 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 = 1000000007; typedef pair<int, int> II; typedef Triple<int> TI; #define maxn 300005 int n; II f[maxn]; II A[maxn]; vector<int> V; pair<int, II> que[maxn]; II get(int x){ II res(0, 1); for(int i = x; i > 0; i -= i & -i){ if(res.fi < f[i].fi) res = f[i]; else if(res.fi == f[i].fi) res.se = (res.se + f[i].se) % mod; } res.fi ++; return res; } void update(int x, II P){ for(int i = x; i < maxn; i += i & -i){ if(f[i].fi < P.fi) f[i] = P; else if(f[i].fi == P.fi) f[i].se = (f[i].se + P.se) % mod; } } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); gi(n); Rep(i, n) { gi(A[i].fi); gi(A[i].se); V.pb(A[i].se);} sort(A, A + n); sort(all(V)); int size = 0; int u, v; II t; II P, res(0, 0); //Rep(i, n) printf("%d %d\n", A[i].fi, A[i].se); Rep(i, n){ u = lower_bound(all(V), A[i].se) - V.begin() + 1; t = get(u - 1); // cout << u << " +++ " << t.fi << " ___ " << t.se << endl; if(t.fi > res.fi) res = t; else if(t.fi == res.fi) res.se = (res.se + t.se) % mod; que[size++] = mp(u, t); if(i != n - 1 && A[i + 1].fi > A[i].fi){ Rep(run, size) update(que[run].fi, que[run].se); size = 0; } } printf("%d\n%d", res.fi, res.se); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; const int MOD = 1000000007; struct Data { int m, s; }; int n; pair<int,int> a[300030]; int py[300030], F[300030], S[300030]; Data it[300030 * 4]; inline Data merge(Data a, Data b) { if(a.m > b.m) return a; else if(a.m < b.m) return b; else { a.s = (a.s + b.s) % MOD; return a; } } void update(int i, int l, int r, int p, int v, int s) { if(l==r) { if(it[i].m==v) it[i].s = (it[i].s+s) % MOD; else if(it[i].m<v) { it[i].m = v; it[i].s = s; } return; } int m = (l+r) / 2; if(p<=m) update(2*i,l,m,p,v,s); if(m<p) update(2*i+1,m+1,r,p,v,s); it[i] = merge(it[2*i], it[2*i+1]); } Data get(int i, int l, int r, int ct) { if(r<=ct) return it[i]; int m = (l+r) / 2; if(m>=ct) return get(2*i,l,m,ct); else return merge(get(2*i,l,m,ct),get(2*i+1,m+1,r,ct)); } int main() { scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d%d", &a[i].first, &a[i].second); py[i] = a[i].second; } sort(a, a+n); sort(py, py+n); for(int i=0;i<n;++i) a[i].second = lower_bound( py, py + n, a[i].second) - py; for(int i=0;i<n;++i) if(i==0 || a[i].first!=a[i-1].first) { for(int j=i;j<n && a[j].first==a[i].first;++j) { Data d; if(a[j].second>0) d = get(1,0,n-1,a[j].second-1); else d.m = 0; F[j] = d.m + 1; if(F[j]==1) S[j] = 1; else S[j] = d.s; } for(int j=i;j<n && a[j].first==a[i].first;++j) update(1,0,n-1,a[j].second,F[j],S[j]); } int res = *max_element( F, F+n); int sum = 0; for(int i=0;i<n;++i) if(F[i]==res) sum = (sum + S[i]) % MOD; printf("%d\n%d\n", res, sum); return 0; }
Bình luận