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;   
}