Cod sursa(job #2865324)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 8 martie 2022 18:41:30
Problema Grendizer Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

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

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

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

int n, m, r, saux, daux, lft, rgt, sol;

int st, md, dr;
int cautbin(vector <int> cb, int target){
    st = 0;
    dr = (int)cb.size()-1;
    while(st <= dr){
        md = ((st+dr)>>1);
        if(cb[md] == target) return md;
        if(cb[md] <  target) st = md + 1;
        if(cb[md] >  target) dr = md - 1;
    }
    return INF;
}

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

    fin>>n>>m;
    for(int i=1; i<=n; i++){
        fin>>p[i].x>>p[i].y;
        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(int i=1; i<=n; i++){
        vs[ cautbin(sum, p[i].x+p[i].y) ].push_back(p[i].x);
        vd[ cautbin(dif, p[i].x-p[i].y) ].push_back(p[i].x);
    }
    for(int i=0; i < (int)sum.size(); i++){
        sort(vs[i].begin(), vs[i].end());
        sort(vd[i].begin(), vd[i].end());
    }

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

        ///latura rombului nord-vest => sum(x, y) e constanta

        saux = cautbin(sum, q.x+q.y-r);
        if(saux != INF){ ///exista elemente cu suma fixata in vs[saux]
            lft = q.x-r;
            rgt = q.x;
            sol += upper_bound(vs[saux].begin(), vs[saux].end(), rgt) - lower_bound(vs[saux].begin(), vs[saux].end(), lft);
        }

        ///latura rombului nord-est  => dif(x, y) e constanta
        daux = cautbin(dif, q.x-q.y-r);
        if(daux != INF){ ///exista elemente cu diff fixata in vd[daux]
            lft = q.x-r;
            rgt = q.x;
            sol += upper_bound(vd[daux].begin(), vd[daux].end(), rgt) - lower_bound(vd[daux].begin(), vd[daux].end(), lft);
        }

        ///latura rombului sud-est   => sum(x, y) e constanta
        saux = cautbin(sum, q.x+q.y+r);
        if(saux != INF){ ///exista elemente cu suma fixata in vs[saux]
            lft = q.x;
            rgt = q.x+r;
            sol += upper_bound(vs[saux].begin(), vs[saux].end(), rgt) - lower_bound(vs[saux].begin(), vs[saux].end(), lft);
        }

        ///latura rombului sud-vest  => dif(x, y) e constanta
        daux = cautbin(dif, q.x-q.y+r);
        if(daux != INF){ ///exista elemente cu diff fixata in vd[daux]
            lft = q.x;
            rgt = q.x+r;
            sol += upper_bound(vd[daux].begin(), vd[daux].end(), rgt) - lower_bound(vd[daux].begin(), vd[daux].end(), lft);
        }

        fout<<sol<<"\n";
    }
    return 0;
}
/**
      13
   22 23 24
31 32 33 34 35
   42 43 44
      53

x = 3
y = 3
r = 2
**/