Dang_Quan_10_Tin

EQ

Aug 7th, 2020
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #define task "EQ"
  6. using namespace std;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. const int N = 5e5 + 2;
  11. const int M = 5e3 + 2;
  12.  
  13. int n, m, k;
  14. struct house{
  15.     ll x, y;
  16.     bool operator < (const house &a) const{
  17.         return y < a.y ||
  18.             (y == a.y && x < a.x);
  19.     }
  20. };
  21. struct quake{
  22.     ll x, y, f;
  23.     bool operator < (const quake &a) const{
  24.         return y < a.y ||
  25.             (y == a.y && x < a.x);
  26.     }
  27. };
  28. using Pquake = quake*;
  29. using Phouse = house*;
  30.  
  31. house a[N];
  32. quake b[M];
  33. const int LIM = 1000;
  34. int ans[N];
  35. bool ck[LIM];
  36.  
  37. ll bp(ll v){
  38.     return v * v;
  39. }
  40.  
  41. void Read(){
  42.     cin >> n >> m >> k;
  43.     for(int i = 1; i <= n; ++i)
  44.         cin >> a[i].x >> a[i].y,
  45.         ck[a[i].y] = 1;
  46.     for(int i = 1; i <= m; ++i){
  47.         cin >> b[i].x >> b[i].y >> b[i].f;
  48.         if(b[i].f > LIM){
  49.             ++ans[1];
  50.             --i;
  51.             --m;
  52.         }
  53.         b[i].f = bp(bp(b[i].f));
  54.     }
  55.     sort(a + 1, a + n + 1);
  56. }
  57.  
  58. void Solve(){
  59.     for(int i = 1; i <= m; ++i)
  60.         for(int j = 0; j <= 100; ++j)
  61.             if(ck[j] && b[i].f >=  bp(j - b[i].y)){
  62.                 int l = 1, m, h = n;
  63.                 while(l <= h){
  64.                     m = (l + h) / 2;
  65.                     if(a[m].y < j) l = m + 1;
  66.                     else h = m - 1;
  67.                 }
  68.                 int piv1 = l;
  69.                 h = n;
  70.                 while(l <= h){
  71.                     m = (l + h) / 2;
  72.                     if(a[m].y <= j) l = m + 1;
  73.                     else h = m - 1;
  74.                 }
  75.                 l = piv1;
  76.                 ll v = b[i].x + (ll)sqrt((ld)(b[i].f - bp(j - b[i].y)));
  77.                 while(l <= h){
  78.                     m = (l + h) / 2;
  79.                     if(a[m].x <= v) l = m + 1;
  80.                     else h = m - 1;
  81.                 }
  82.                 v = b[i].x - (ll)sqrt((ld)(b[i].f - bp(j - b[i].y)));
  83.                 l = piv1;
  84.                 int piv2 = h;
  85.                 while(l <= h){
  86.                     m = (l + h) / 2;
  87.                     if(a[m].x < v) l = m + 1;
  88.                     else h = m - 1;
  89.                 }
  90.                 if(l <= piv2){
  91.                     ++ans[l];
  92.                     --ans[piv2 + 1];
  93.                 }
  94.             }
  95.     int res = 0;
  96.     for(int i = 1; i <= n; ++i){
  97.         ans[i] += ans[i - 1];
  98.         if(ans[i] >= k)
  99.             ++res;
  100.     }
  101.     cout << res;
  102. }
  103.  
  104. int32_t main(){
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     cout.tie(0); if(fopen(task".INP", "r"))
  108.     freopen(task".INP", "r", stdin),
  109.     freopen(task".OUT", "w", stdout);
  110.     Read();
  111.     Solve();
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment