Advertisement
willy108

buggy discretization

Mar 17th, 2022
957
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1.  
  2. //stupid robot grid
  3.  
  4. //misaka will carry me to master
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <utility>
  10. #include <cassert>
  11. #include <algorithm>
  12. #include <vector>
  13. #include <functional>
  14. #include <numeric>
  15. #include <set>
  16. #include <map>
  17.  
  18. #define ll long long
  19. #define lb long double
  20. #define sz(vec) ((int)(vec.size()))
  21. #define all(x) x.begin(), x.end()
  22. #define pb push_back
  23. #define mp make_pair
  24. #define ff first
  25. #define ss second
  26. //probably useful
  27.  
  28. const lb eps = 1e-9;
  29. const ll mod = 1e9 + 7, ll_max = 1e18;
  30. //const ll mod = (1 << (23)) * 119 +1;
  31. const int MX = 4e5 +10, int_max = 0x3f3f3f3f;
  32.  
  33. using namespace std;
  34.  
  35.  
  36. struct disc{
  37.     static vector<int> vals;
  38.     disc(){}
  39.     static void add(int x){
  40.         vals.pb(x);
  41.     }
  42.     static void norm(){
  43.         sort(all(vals));
  44.         vals.resize(unique(all(vals)) - vals.begin());
  45.     }
  46.     static int gind(int x){
  47.         assert(binary_search(all(vals), x));
  48.         return lower_bound(all(vals), x) - vals.begin();
  49.     }
  50.     static int zz(){
  51.         return sz(vals);
  52.     }
  53. };
  54. //parallel to x axis is 0
  55. //            y axis is 1
  56. struct segment{
  57.     int dir;
  58.     int pos;
  59.     int l, r;
  60.     segment(){}
  61.     segment(int a, int b, int c, int d){
  62.         dir = a, pos = b, l = c, r = d;
  63.     }
  64. } seg[MX];
  65.  
  66.  
  67. const int NN = MX*40; //yes
  68. /** pst **/
  69. int lc[MX], rc[MX], leaf[MX];
  70. int IND = 1;
  71. int n, m, K, q, s;
  72.  
  73. void dup(int& k){
  74.     IND++;
  75.     lc[IND] = lc[k];
  76.     rc[IND] = rc[k];
  77.     leaf[IND] = leaf[k];
  78.     k = IND;
  79. }
  80.  
  81. void U(int p, int v, int& k, int L, int R){
  82.     if(R <= L) return ;
  83.     dup(k);
  84.     if(L + 1 == R){
  85.         assert(L == p);
  86.         leaf[k] = v;
  87.         return ;
  88.     }
  89.     int mid = (L + R)/2;
  90.     if(p < mid) U(p, v, lc[k], L, mid);
  91.     else U(p, v, rc[k], mid, R);
  92.     //no pull needed i think
  93. }
  94.  
  95. void Q(int qL, int qR, vector<int>& e, int k, int L, int R){
  96.     if(qR <= L || R <= qL || R <= L || qR <= qL || k == 0) return ;
  97.     if(qL <= L && R <= qR){
  98.         e.pb(k);
  99.         return ;
  100.     }
  101.     int mid = (L + R)/2;
  102.     Q(qL, qR, e, lc[k], L, mid);
  103.     Q(qL, qR, e, rc[k], mid, R);
  104. }
  105.  
  106. /** relevant to problem **/
  107. #define pii pair<int, int>
  108. vector<pii> points, queries;
  109. pii source;
  110.  
  111. void solve(){
  112.     cin >> n >> m >> K >> q;
  113.     for(int i = 0; i<K; i++){
  114.         int a, b;
  115.         cin >> a >> b;
  116.         points.pb(mp(a, b));
  117.         disc::add(a);
  118.         disc::add(b);
  119.     }
  120.     cin >> source.ff >> source.ss;
  121.     disc::add(source.ff);
  122.     disc::add(source.ss);
  123.     for(int i = 0; i<q; i++){
  124.         int a, b;
  125.         cin >> a >> b;
  126.         disc::add(a);
  127.         disc::add(b);
  128.         queries.pb(mp(a, b));
  129.     }
  130.     disc::norm();
  131.     for(int i = 0; i<K; i++){
  132.         points[i] = mp(disc::gind(points[i].ff), disc::gind(points[i].ss));
  133.     }
  134.     for(int i = 0; i<q; i++){
  135.         queries[i] = mp(disc::gind(queries[i].ff), disc::gind(queries[i].ss));
  136.     }
  137.     source = mp(disc::gind(source.ff), disc::gind(source.ss));
  138. }
  139.  
  140. int main(){
  141.   cin.tie(0) -> sync_with_stdio(0);
  142.  
  143.   int T = 1;
  144.   //cin >> T;
  145.   while(T--){
  146.         solve();
  147.   }
  148.   return 0;
  149. }
  150.  
  151.  
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement