Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //stupid robot grid
- //misaka will carry me to master
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <utility>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <functional>
- #include <numeric>
- #include <set>
- #include <map>
- #define ll long long
- #define lb long double
- #define sz(vec) ((int)(vec.size()))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- //probably useful
- const lb eps = 1e-9;
- const ll mod = 1e9 + 7, ll_max = 1e18;
- //const ll mod = (1 << (23)) * 119 +1;
- const int MX = 4e5 +10, int_max = 0x3f3f3f3f;
- using namespace std;
- struct disc{
- static vector<int> vals;
- disc(){}
- static void add(int x){
- vals.pb(x);
- }
- static void norm(){
- sort(all(vals));
- vals.resize(unique(all(vals)) - vals.begin());
- }
- static int gind(int x){
- assert(binary_search(all(vals), x));
- return lower_bound(all(vals), x) - vals.begin();
- }
- static int zz(){
- return sz(vals);
- }
- };
- //parallel to x axis is 0
- // y axis is 1
- struct segment{
- int dir;
- int pos;
- int l, r;
- segment(){}
- segment(int a, int b, int c, int d){
- dir = a, pos = b, l = c, r = d;
- }
- } seg[MX];
- const int NN = MX*40; //yes
- /** pst **/
- int lc[MX], rc[MX], leaf[MX];
- int IND = 1;
- int n, m, K, q, s;
- void dup(int& k){
- IND++;
- lc[IND] = lc[k];
- rc[IND] = rc[k];
- leaf[IND] = leaf[k];
- k = IND;
- }
- void U(int p, int v, int& k, int L, int R){
- if(R <= L) return ;
- dup(k);
- if(L + 1 == R){
- assert(L == p);
- leaf[k] = v;
- return ;
- }
- int mid = (L + R)/2;
- if(p < mid) U(p, v, lc[k], L, mid);
- else U(p, v, rc[k], mid, R);
- //no pull needed i think
- }
- void Q(int qL, int qR, vector<int>& e, int k, int L, int R){
- if(qR <= L || R <= qL || R <= L || qR <= qL || k == 0) return ;
- if(qL <= L && R <= qR){
- e.pb(k);
- return ;
- }
- int mid = (L + R)/2;
- Q(qL, qR, e, lc[k], L, mid);
- Q(qL, qR, e, rc[k], mid, R);
- }
- /** relevant to problem **/
- #define pii pair<int, int>
- vector<pii> points, queries;
- pii source;
- void solve(){
- cin >> n >> m >> K >> q;
- for(int i = 0; i<K; i++){
- int a, b;
- cin >> a >> b;
- points.pb(mp(a, b));
- disc::add(a);
- disc::add(b);
- }
- cin >> source.ff >> source.ss;
- disc::add(source.ff);
- disc::add(source.ss);
- for(int i = 0; i<q; i++){
- int a, b;
- cin >> a >> b;
- disc::add(a);
- disc::add(b);
- queries.pb(mp(a, b));
- }
- disc::norm();
- for(int i = 0; i<K; i++){
- points[i] = mp(disc::gind(points[i].ff), disc::gind(points[i].ss));
- }
- for(int i = 0; i<q; i++){
- queries[i] = mp(disc::gind(queries[i].ff), disc::gind(queries[i].ss));
- }
- source = mp(disc::gind(source.ff), disc::gind(source.ss));
- }
- int main(){
- cin.tie(0) -> sync_with_stdio(0);
- int T = 1;
- //cin >> T;
- while(T--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement