Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- #define task "EQ"
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 5e5 + 2;
- const int M = 5e3 + 2;
- int n, m, k;
- struct house{
- ll x, y;
- bool operator < (const house &a) const{
- return y < a.y ||
- (y == a.y && x < a.x);
- }
- };
- struct quake{
- ll x, y, f;
- bool operator < (const quake &a) const{
- return y < a.y ||
- (y == a.y && x < a.x);
- }
- };
- using Pquake = quake*;
- using Phouse = house*;
- house a[N];
- quake b[M];
- const int LIM = 1000;
- int ans[N];
- bool ck[LIM];
- ll bp(ll v){
- return v * v;
- }
- void Read(){
- cin >> n >> m >> k;
- for(int i = 1; i <= n; ++i)
- cin >> a[i].x >> a[i].y,
- ck[a[i].y] = 1;
- for(int i = 1; i <= m; ++i){
- cin >> b[i].x >> b[i].y >> b[i].f;
- if(b[i].f > LIM){
- ++ans[1];
- --i;
- --m;
- }
- b[i].f = bp(bp(b[i].f));
- }
- sort(a + 1, a + n + 1);
- }
- void Solve(){
- for(int i = 1; i <= m; ++i)
- for(int j = 0; j <= 100; ++j)
- if(ck[j] && b[i].f >= bp(j - b[i].y)){
- int l = 1, m, h = n;
- while(l <= h){
- m = (l + h) / 2;
- if(a[m].y < j) l = m + 1;
- else h = m - 1;
- }
- int piv1 = l;
- h = n;
- while(l <= h){
- m = (l + h) / 2;
- if(a[m].y <= j) l = m + 1;
- else h = m - 1;
- }
- l = piv1;
- ll v = b[i].x + (ll)sqrt((ld)(b[i].f - bp(j - b[i].y)));
- while(l <= h){
- m = (l + h) / 2;
- if(a[m].x <= v) l = m + 1;
- else h = m - 1;
- }
- v = b[i].x - (ll)sqrt((ld)(b[i].f - bp(j - b[i].y)));
- l = piv1;
- int piv2 = h;
- while(l <= h){
- m = (l + h) / 2;
- if(a[m].x < v) l = m + 1;
- else h = m - 1;
- }
- if(l <= piv2){
- ++ans[l];
- --ans[piv2 + 1];
- }
- }
- int res = 0;
- for(int i = 1; i <= n; ++i){
- ans[i] += ans[i - 1];
- if(ans[i] >= k)
- ++res;
- }
- cout << res;
- }
- int32_t main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0); if(fopen(task".INP", "r"))
- freopen(task".INP", "r", stdin),
- freopen(task".OUT", "w", stdout);
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment