Editorial for Điểm trên cạnh hình chữ nhật - HRASTOVI
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
const fi=''; fo=''; maxn=300300; maxm=200200; oo=1000000000; type ar1=array[1..maxn] of longint; ar2=array[1..maxm] of longint; var num,numy,n,m:longint; x,y:ar1; a,b,re:ar2; procedure rf; var i:longint; begin read(n); for i:=1 to n do read(x[i],y[i]); read(m); for i:=1 to m do read(a[i*2],b[i*2],a[i*2+1],b[i*2+1]); end; procedure sort(l,r:longint); var i,j,p,q,t:longint; begin i:=l; j:=r; p:=x[(i+j) shr 1]; q:=y[(i+j) shr 1]; repeat while (x[i]<p) or ((x[i]=p) and (y[i]<q)) do i:=i+1; while (x[j]>p) or ((x[j]=p) and (y[j]>q)) do j:=j-1; if i<=j then begin t:=x[i]; x[i]:=x[j]; x[j]:=t; t:=y[i]; y[i]:=y[j]; y[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,p,q,t:longint; begin i:=l; j:=r; p:=y[(i+j) shr 1]; q:=x[(i+j) shr 1]; repeat while (y[i]<p) or ((y[i]=p) and (x[i]<q)) do i:=i+1; while (y[j]>p) or ((y[j]=p) and (x[j]>q)) do j:=j-1; if i<=j then begin t:=x[i]; x[i]:=x[j]; x[j]:=t; t:=y[i]; y[i]:=y[j]; y[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; function bs(xx,yy:longint):longint; var l,r,mid,i:longint; begin bs:=oo; l:=1; r:=n; while l<=r do begin mid:=(l+r) div 2; if (x[mid]<xx) or ((x[mid]=xx) and (y[mid]<yy)) then l:=mid+1 else r:=mid-1; end; for i:=mid-1 to mid+1 do if (i>0) and (i<=n) and ((x[i]>xx) or ((x[i]=xx) and (y[i]>=yy))) then exit(i); end; function bss(xx,yy:longint):longint; var l,r,mid,i:longint; begin bss:=-oo; l:=1; r:=n; while l<=r do begin mid:=(l+r) div 2; if (x[mid]>xx) or ((x[mid]=xx) and (y[mid]>yy)) then r:=mid-1 else l:=mid+1; end; for i:=mid+1 downto mid-1 do if (i>0) and (i<=n) and ((x[i]<xx) or ((x[i]=xx) and (y[i]<=yy))) then exit(i); end; procedure pr; var i,p,q:longint; begin for i:=1 to m do begin p:=bs(a[i*2],b[i*2]); q:=bss(a[i*2],b[i*2+1]); if q>=p then re[i]:=re[i]+q-p+1; p:=bs(a[i*2+1],b[i*2]); q:=bss(a[i*2+1],b[i*2+1]); if q>=p then re[i]:=re[i]+q-p+1; end; end; function bs1(xx,yy:longint):longint; var l,r,mid,i:longint; begin bs1:=oo; l:=1; r:=n; while l<=r do begin mid:=(l+r) div 2; if (y[mid]<yy) or ((y[mid]=yy) and (x[mid]<xx)) then l:=mid+1 else r:=mid-1; end; for i:=mid-1 to mid+1 do if (i>0) and (i<=n) and ((y[i]>yy) or ((y[i]=yy) and (x[i]>=xx))) then exit(i); end; function bss1(xx,yy:longint):longint; var l,r,mid,i:longint; begin bss1:=-oo; l:=1; r:=n; while l<=r do begin mid:=(l+r) div 2; if (y[mid]>yy) or ((y[mid]=yy) and (x[mid]>xx)) then r:=mid-1 else l:=mid+1; end; for i:=mid+1 downto mid-1 do if (i>0) and (i<=n) and ((y[i]<yy) or ((y[i]=yy) and (x[i]<=xx))) then exit(i); end; procedure prr; var i,p,q:longint; begin for i:=1 to m do begin p:=bs1(a[i*2],b[i*2]); q:=bss1(a[i*2+1],b[i*2]); if q>=p then re[i]:=re[i]+q-p+1; p:=bs1(a[i*2],b[i*2+1]); q:=bss1(a[i*2+1],b[i*2+1]); if q>=p then re[i]:=re[i]+q-p+1; end; end; function bsss(xx,yy:longint):boolean; var l,r,mid:longint; begin bsss:=false; l:=1; r:=n; while l<=r do begin mid:=(l+r) div 2; if (x[mid]=xx) and (y[mid]=yy) then exit(true); if (x[mid]<xx) or ((x[mid]=xx) and (y[mid]<yy)) then l:=mid+1 else r:=mid-1; end; end; procedure minus; var i:longint; begin for i:=1 to m do begin if bsss(a[i*2],b[i*2]) then re[i]:=re[i]-1; if bsss(a[i*2],b[i*2+1]) then re[i]:=re[i]-1; if bsss(a[i*2+1],b[i*2]) then re[i]:=re[i]-1; if bsss(a[i*2+1],b[i*2+1]) then re[i]:=re[i]-1; end; end; procedure wf; var i:longint; begin for i:=1 to m do writeln(re[i]); end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); rf; sort(1,n); minus; pr; sortt(1,n); prr; wf; close(input); close(output); end.
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> //#include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 700005; using namespace std; int n, m, p; int x1[N], y1[N], x2[N], y2[N]; struct point { int x, y, id; point(int _x = 0, int _y = 0, int _id = 0) { x = _x; y = _y; id = _id; } bool operator < (const point &b) const { return (x != b.x) ? (x < b.x) : ((y != b.y) ? (y < b.y) : id < b.id); } } a[N]; int findLeft(point a) { if (a.y == y1[a.id]) return -1; return y1[a.id]; } int s[N]; int ans[N]; void solve() { sort(a + 1, a + 1 + p); int j; for(int i = 1; i <= p; i = j + 1) { j = i; while (a[j + 1].x == a[i].x) j++; s[i - 1] = 0; REP(k, i, j) { s[k] = s[k - 1]; if (a[k].id) { int l = i, r = k, pos; int leftBound = findLeft(a[k]); if (leftBound == -1) continue; while (l <= r) { int mid = l + r >> 1; if (a[mid].y >= leftBound) { pos = mid; r = mid - 1; } else l = mid + 1; } ans[a[k].id] += s[k] - s[pos - 1]; } else s[k]++; } } } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; REP(i, 1, n) cin >> a[i].x >> a[i].y; cin >> m; p = n; REP(i, 1, m) { cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]; a[++p] = point(x1[i], y1[i], i); a[++p] = point(x1[i], y2[i], i); a[++p] = point(x2[i], y1[i], i); a[++p] = point(x2[i], y2[i], i); } solve(); REP(i, 1, p) swap(a[i].x, a[i].y); REP(i, 1, m) { int yy1 = y1[i], yy2 = y2[i]; y1[i] = x1[i]; y2[i] = x2[i]; x1[i] = yy2; x2[i] = yy1; } solve(); int j; for(int i = 1; i <= p; i = j + 1) { j = i; if (a[i].id == 0) { while (a[j + 1].x == a[i].x && a[j + 1].y == a[i].y) ans[a[++j].id]--; } } REP(i, 1, m) cout << ans[i] << '\n'; return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstdio> #define MAXN 300111 #define FOR(i,a,b) for(int i=a; i<=b; i++) #define MP make_pair #define UB upper_bound #define LB lower_bound #define oo 1000111000 using namespace std; int n,m; pair<int,int> a[MAXN],b[MAXN]; int main() { scanf("%d",&n); FOR(i,1,n) { int x,y; scanf("%d %d",&x,&y); a[i]=MP(x,y); b[i]=MP(y,x); } n++; a[n]=MP(oo,oo); b[n]=MP(oo,oo); sort(a+1,a+n+1); sort(b+1,b+n+1); scanf("%d",&m); FOR(i,1,m) { int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); int res=UB(a+1,a+n+1,MP(x1,y2))-LB(a+1,a+n+1,MP(x1,y1)) +UB(a+1,a+n+1,MP(x2,y2))-LB(a+1,a+n+1,MP(x2,y1)) +UB(b+1,b+n+1,MP(y1,x2-1))-LB(b+1,b+n+1,MP(y1,x1+1)) +UB(b+1,b+n+1,MP(y2,x2-1))-LB(b+1,b+n+1,MP(y2,x1+1)); printf("%d\n",res); } return 0; }
Code mẫu của hieult
#include <cstdio> #include <vector> #include <cstdlib> #include <algorithm> //#include <conio.h> using namespace std; vector<pair < int, int> > X,Y; int n,que,x,y,x1,x2,y1,y2; inline int Q_fow(vector<pair<int,int> > &P, int x,int y1,int y2){ return upper_bound(P.begin(),P.end(),make_pair(x,y2))- upper_bound(P.begin(),P.end(),make_pair(x,y1)); } inline int Q_rev(vector<pair<int,int> > &P,int x, int y1,int y2){ return lower_bound(P.begin(),P.end(),make_pair(x,y2))-lower_bound(P.begin(),P.end(),make_pair(x,y1)); } int main() { scanf("%d",&n); for(int i = 0;i<n;i++) { scanf("%d %d",&x,&y); X.push_back(make_pair(x,y)); Y.push_back(make_pair(y,x)); } sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); scanf("%d",&que); for(int i = 1;i<=que;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); printf("%d\n",Q_fow(X,x1,y1,y2)+Q_fow(Y,y2,x1,x2)+Q_rev(X,x2,y1,y2)+Q_rev(Y,y1,x1,x2)); } // getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> typedef long long ll; using namespace std; vector< pair<int,int> > X,Y; int n,p; int segX(pair<int,int> u,pair<int,int> v) { return upper_bound(X.begin(),X.end(),v) - lower_bound(X.begin(),X.end(),u); }; int segY(pair<int,int> u,pair<int,int> v) { return upper_bound(Y.begin(),Y.end(),v) - lower_bound(Y.begin(),Y.end(),u); }; int main() { // freopen("hras.in","r",stdin); // freopen("hras.ou","w",stdout); scanf("%d", &n); for (int i = 0; i < n; i++) { int x,y; scanf("%d %d", &x, &y); X.push_back(make_pair(x,y)); Y.push_back(make_pair(y,x)); }; sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); scanf("%d", &p); for (int i = 0; i < p; i++) { int x1,y1,x2,y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); int ret = 0; ret += segX(make_pair(x1,y1),make_pair(x1,y2)); ret += segX(make_pair(x2,y1),make_pair(x2,y2)); ret += segY(make_pair(y1,x1 + 1),make_pair(y1,x2 - 1)); ret += segY(make_pair(y2,x1 + 1),make_pair(y2,x2 - 1)); printf("%d\n", ret); }; };
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAXP 300300 #define MAXR 100100 #define x first #define y second using namespace std; typedef pair<int,int> point; point ax[MAXP]; point ay[MAXP]; int n,p; bool cmpx(const point &a,const point &b) { if (a.x<b.x) return (true); if (a.x>b.x) return (false); return (a.y<b.y); } bool cmpy(const point &a,const point &b) { if (a.y<b.y) return (true); if (a.y>b.y) return (false); return (a.x<b.x); } void init(void) { int i,px,py; scanf("%d",&n); for (i=1;i<=n;i=i+1) { scanf("%d",&px); scanf("%d",&py); ax[i]=point(px,py); ay[i]=point(px,py); } sort(&ax[1],&ax[n+1],cmpx); sort(&ay[1],&ay[n+1],cmpy); } int county(const int &y,const int &x1,const int &x2) { if (x1>x2) return (0); if (cmpy(ay[n],point(x1,y))) return (0); if (cmpy(point(x2,y),ay[1])) return (0); int f,l; f=lower_bound(&ay[1],&ay[n+1],point(x1,y),cmpy)-&ay[0]; if (cmpy(point(x2,y),ay[n])) l=upper_bound(&ay[1],&ay[n+1],point(x2,y),cmpy)-&ay[0]; else l=n+1; return (l-f); } int countx(const int &x,const int &y1,const int &y2) { if (y1>y2) return (0); if (cmpx(ax[n],point(x,y1))) return (0); if (cmpx(point(x,y2),ax[1])) return (0); int f,l; f=lower_bound(&ax[1],&ax[n+1],point(x,y1),cmpx)-&ax[0]; if (cmpx(point(x,y2),ax[n])) l=upper_bound(&ax[1],&ax[n+1],point(x,y2),cmpx)-&ax[0]; else l=n+1; return (l-f); } void process(void) { int i,r,x1,y1,x2,y2; scanf("%d",&p); for (i=1;i<=p;i=i+1) { r=0; scanf("%d",&x1); scanf("%d",&y1); scanf("%d",&x2); scanf("%d",&y2); r+=county(y1,x1,x2); r+=county(y2,x1,x2); r+=countx(x1,y1+1,y2-1); r+=countx(x2,y1+1,y2-1); printf("%d\n",r); } } int main(void) { init(); process(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <sstream> #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 typedef pair<int,int> PII; typedef vector<int> VI; struct Rect { int x, y, u, v; }; struct Seg { int id; int x; int y1, y2; bool operator<(Seg s)const{ return x<s.x; } }; int n, m; PII a[300030]; Rect b[100010]; Seg s[200020]; int res[100010]; int ns; int dx[300030]; int nd; int bit[300030]; void update(int i,int dt) { for(++i;i<300030;i+=i&(-i))bit[i]+=dt; } int calc(int i){ int r=0; for(++i;i>0;i-=i&(-i))r+=bit[i]; return r; } int main() { scanf("%d",&n); Rep(i,n)scanf("%d%d",&a[i].first,&a[i].second); scanf("%d",&m); Rep(i,m){ scanf("%d%d%d%d",&b[i].x,&b[i].y,&b[i].u,&b[i].v); } for(int kk=0;kk<2;++kk) { sort(a,a+n); nd = 0; Rep(i,n) dx[nd++] = a[i].second; sort(dx, dx + nd); nd = unique(dx,dx+nd)-dx; memset(bit,0,sizeof(bit)); // cout << nd << endl; ns = 0; Rep(i,m){ s[ns].id = i; s[ns].x=b[i].x; s[ns].y1=b[i].y; s[ns].y2=b[i].v; ++ns; s[ns]=s[ns-1]; s[ns].x=b[i].u; ++ns; } sort(s,s+ns); int sin = 0, sout = 0; for(int i=0;i<ns;){ int j=i; while(j<ns && s[j].x==s[i].x) ++j; while(sin < n && a[sin].first <= s[i].x) { update(lower_bound(dx,dx+nd,a[sin].second)-dx,1); ++sin; } while(sout<n && a[sout].first < s[i].x) { update(lower_bound(dx,dx+nd,a[sout].second)-dx,-1); ++sout; } for(int k=i;k<j;++k) { int id1 = upper_bound(dx,dx+nd,s[k].y1)-dx; int id2 = lower_bound(dx,dx+nd,s[k].y2)-dx-1; // cout << " here " << id1 << " " << id2 << endl; if(id1<=id2) res[s[k].id] += calc(id2) - calc(id1-1); } i=j; } Rep(i,n) swap(a[i].first,a[i].second); Rep(i,m) swap(b[i].x,b[i].y), swap(b[i].u,b[i].v); } sort(a,a+n); Rep(i,m){ if(binary_search(a,a+n,MP(b[i].x,b[i].y))) ++res[i]; if(binary_search(a,a+n,MP(b[i].x,b[i].v))) ++res[i]; if(binary_search(a,a+n,MP(b[i].u,b[i].y))) ++res[i]; if(binary_search(a,a+n,MP(b[i].u,b[i].v))) ++res[i]; } for(int i=0;i<m;++i) printf("%d\n",res[i]); return 0; }
Comments