Cod sursa(job #2865391)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 8 martie 2022 19:46:23
Problema Grendizer Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.95 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define LL long long

using namespace std;

ifstream fin  ("grendizer.in");
ofstream fout ("grendizer.out");

const LL INF = 2e9+1;
const LL MAX_N = 100005;

struct punct{
    LL x;
    LL y;
} q, p[MAX_N];

inline bool cmp(const punct& a, const punct& b){
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

vector <LL> sum, dif;
vector <LL> vs[MAX_N], vd[MAX_N];

LL n, m, r, poz, sol;

LL st, md, dr, lft, rgt;
LL caut_sum(LL target){
    st = 0;
    dr = (LL)sum.size()-1;
    while(st <= dr){
        md = ((st+dr)>>1);
        if(sum[md] == target) return md;
        if(sum[md] <  target) st = md + 1;
        if(sum[md] >  target) dr = md - 1;
    }
    return INF;
}
LL caut_dif(LL target){
    st = 0;
    dr = (LL)dif.size()-1;
    while(st <= dr){
        md = ((st+dr)>>1);
        if(dif[md] == target) return md;
        if(dif[md] <  target) st = md + 1;
        if(dif[md] >  target) dr = md - 1;
    }
    return INF;
}
bool caut_pct(const LL& tx, const LL& ty){
    lft = -1;
    st = 1;
    dr = n;
    while(st <= dr){
        md = ((st+dr)>>1);
        if(p[md].x < tx)
            st = md + 1;
        else{
            lft = md;
            dr = md - 1;
        }
    }

    rgt = -1;
    st = 1;
    dr = n;
    while(st <= dr){
        md = ((st+dr)>>1);
        if(p[md].x <= tx){
            rgt = md;
            st = md + 1;
        }else
            dr = md - 1;
    }

    if(lft != -1 && rgt != -1 && p[lft].x == tx && p[rgt].x == tx){
        st = lft;
        dr = rgt;
        while(st <= dr){
            md = ((st+dr)>>1);
            if(p[md].y == ty) return true;
            if(p[md].y <  ty) st = md + 1;
            if(p[md].y >  ty) dr = md - 1;
        }
    }
    return false;
}

signed main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin>>n>>m;
    for(LL i=1; i<=n; i++)
        fin>>p[i].x>>p[i].y;
    sort(p+1, p+n+1, cmp);

    for(LL i=1; i<=n; i++){
        sum.push_back(p[i].x+p[i].y);
        dif.push_back(p[i].x-p[i].y);
    }
    sort(sum.begin(), sum.end());
    sort(dif.begin(), dif.end());

    sum.resize(distance(sum.begin(), unique(sum.begin(), sum.end())));
    dif.resize(distance(dif.begin(), unique(dif.begin(), dif.end())));

    for(LL i=1; i<=n; i++){
        vs[ caut_sum(p[i].x+p[i].y) ].push_back(p[i].x);
        vd[ caut_dif(p[i].x-p[i].y) ].push_back(p[i].x);
    }

    while(m--){
        fin>>q.x>>q.y>>r;
        sol = 0;

        ///NV => diff constanta
        poz = caut_dif(q.x - q.y - r);
        if(poz != INF)
            sol += upper_bound(vd[poz].begin(), vd[poz].end(), q.x) - lower_bound(vd[poz].begin(), vd[poz].end(), q.x-r);

        ///NE => suma constanta
        poz = caut_sum(q.x + q.y + r);
        if(poz != INF)
            sol += upper_bound(vs[poz].begin(), vs[poz].end(), q.x+r) - lower_bound(vs[poz].begin(), vs[poz].end(), q.x);

        ///SE => diff constanta
        poz = caut_dif(q.x - q.y + r);
        if(poz != INF)
            sol += upper_bound(vd[poz].begin(), vd[poz].end(), q.x+r) - lower_bound(vd[poz].begin(), vd[poz].end(), q.x);

        ///SV => suma constanta
        poz = caut_sum(q.x + q.y - r);
        if(poz != INF)
            sol += upper_bound(vs[poz].begin(), vs[poz].end(), q.x) - lower_bound(vs[poz].begin(), vs[poz].end(), q.x-r);

        fout<<sol - caut_pct(q.x, q.y-r) - caut_pct(q.x, q.y+r) - caut_pct(q.x-r, q.y) - caut_pct(q.x+r, q.y)<<"\n";
    }
    return 0;
}
/**
OY
 ^
9|
8|          *(7, 8)     *(x, y)
7|        *(6, 7)          *(x+1, y-1)
6|      *(5, 6)               *(x+2, y-2)
5|    *(4, 5)                    *(x+3, y-3)
4|
3|    *(3, 3)               *(x+1, y+1)
2|      *(4, 2)           *(x+1, y+1)
1|        *(5, 1)       *(x, y)
0*- - - - - - - - -> OX
 01 2 3 4 5 6 7 8 9
x = 3
y = 3
r = 2
**/