fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. #define output(v) for(auto&it:v){cout<<it<<" ";}cout<<"\n"
  11. #define input(v) for(auto&it:v){cin>>it;}
  12. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  13. const int N = 1e6+5;
  14. const int MOD = 1e9+7;
  15. const double pi= 3.1415926535897932;
  16. //======================================================
  17. void FastCode()
  18. {
  19.     std::ios_base::sync_with_stdio(0);
  20.     cin.tie(NULL);
  21.     cout.tie(NULL);
  22. }
  23. //======================================================
  24. struct DSU{
  25.     vector<int> parent;
  26.     vector<int> sizeOfGroup;
  27.     DSU(int N){
  28.         parent.resize(N+5);
  29.         sizeOfGroup.resize(N+5);
  30.         for(int i = 0 ; i < N ; i++){
  31.             parent[i] = i;
  32.             sizeOfGroup[i] = 1;
  33.         }
  34.     }
  35.     ll getLeader(int i){
  36.         if(i == parent[i]) return i;
  37.         else return parent[i] = getLeader(parent[i]);
  38.     }
  39.     bool sameGroup(int x , int y){
  40.         return getLeader(x) == getLeader(y);
  41.     }
  42.     void mergeGroup(int x , int y){
  43.         int leader1 = getLeader(x);
  44.         int leader2 = getLeader(y);
  45.         if(leader1 == leader2) return;
  46.         else if(sizeOfGroup[leader1]>sizeOfGroup[leader2]){
  47.             parent[leader2] = leader1;
  48.             sizeOfGroup[leader1]+=sizeOfGroup[leader2];
  49.         }else{
  50.             parent[leader1] = leader2;
  51.             sizeOfGroup[leader2]+=sizeOfGroup[leader1];
  52.         }
  53.     }
  54.     int getSize(int x){
  55.         return sizeOfGroup[getLeader(x)];
  56.     }
  57.  
  58. };
  59. //======================================================
  60. struct FenwickTree{
  61.     vector<ll> arr;
  62.     int n;
  63.     FenwickTree(int N){
  64.         n=N;
  65.         arr.resize(N+5);
  66.     }
  67.  
  68.     void update(ll idx , ll val){
  69.         while(idx < n+5){
  70.             arr[idx]+=val;
  71.             idx += idx&-idx;
  72.         }
  73.     }
  74.     ll sum(ll idx){
  75.         ll s=0;
  76.         while(idx){
  77.             s+=arr[idx];
  78.             idx -= idx&-idx;
  79.         }
  80.         return s;
  81.     }
  82.     ll sum(ll l , ll r){
  83.         return sum(r)-sum(l-1);
  84.     }
  85.     ll get(int idx){
  86.         return sum(idx)-sum(idx-1);
  87.     }
  88. };
  89. //======================================================
  90. struct SegmentTreeRangeSum{
  91.     int size;
  92.     vector<ll> arr;
  93.     SegmentTreeRangeSum(vector<ll> &a){
  94.         size = 1;
  95.         int n = a.size();
  96.         while(size < n) size *= 2;
  97.         arr.assign(size*2 , 0ll);
  98.         build( a,0,0,size);
  99.     }
  100.     void build(vector<ll> &a , int x , int lx , int rx){
  101.         if(rx-lx == 1){
  102.             if(lx < a.size()) arr[x] = a[lx];
  103.             return;
  104.         }
  105.         int md = (lx+rx)>>1;
  106.         build(a , 2*x+1 , lx , md);
  107.         build(a , 2*x+2 , md , rx);
  108.         arr[x] = arr[2*x+1] + arr[2*x+2];
  109.     }
  110.     void set(int idx , int val , int x , int lx , int rx){
  111.         if(rx-lx == 1){
  112.             arr[x] = val;
  113.             return;
  114.         }
  115.         int md = (lx+rx)>>1;
  116.         if(idx < md){
  117.             set(idx , val , 2*x+1 , lx ,md);
  118.         }else{
  119.             set(idx , val , 2*x+2 , md ,rx);
  120.         }
  121.         arr[x] = arr[2*x+1] + arr[2*x+2];
  122.     }
  123.     void set(int idx , ll val){
  124.         set(idx , val , 0 , 0 , size);
  125.     }
  126.     ll sum(int l , int r, int cur , int lx , int rx){
  127.         if(lx >= r || l >= rx) return 0;
  128.         else if(lx >= l && r >= rx) return  arr[cur];
  129.         int md = (lx+rx)>>1;
  130.         return sum(l , r , 2*cur+1 , lx , md) + sum(l , r , 2*cur+2 , md , rx);
  131.     }
  132.     ll sum(int l , int r){
  133.         return sum(l , r , 0 , 0 , size);
  134.     }
  135. };
  136. //======================================================
  137. struct SegmentTreeMinVal{
  138.     int size;
  139.     vector<pair<ll , int>> tree;
  140.     SegmentTreeMinVal(int n){
  141.         size = 1;
  142.         while(size < n) size *= 2;
  143.         tree.assign(2*size-1 , {LLONG_MAX , 1});
  144.     }
  145.     void insert(int idx , ll val , int x , int lx , int rx){
  146.         if(rx - lx == 1){
  147.             tree[x] = {val , 1};
  148.             return;
  149.         }
  150.         int md = (rx+lx)>>1;
  151.         if(idx < md){
  152.             insert(idx ,val , 2*x+1 , lx , md);
  153.         }else{
  154.             insert(idx ,val , 2*x+2 , md , rx);
  155.         }
  156.         pair<ll , int> p1 = tree[2*x+1];
  157.         pair<ll , int> p2 = tree[2*x+2];
  158.         if(p1.first == p2.first)
  159.             tree[x] = {p1.first , p1.second + p2.second};
  160.         else if(p1.first > p2.first)
  161.             tree[x] = p2;
  162.         else tree[x] = p1;
  163.     }
  164.     void insert(int idx , ll val){
  165.         insert(idx , val , 0 , 0 , size);
  166.     }
  167.     pair<ll , int> getMinVal(int l , int r , int x , int lx , int rx){
  168.         if(lx >= r || l >= rx) return {LLONG_MAX , 1};
  169.         else if(lx >= l && rx <= r) return tree[x];
  170.         else{
  171.             int md = (lx+rx)>>1;
  172.             pair<ll , int> p1 = getMinVal(l , r , 2*x+1 , lx , md);
  173.             pair<ll , int> p2 = getMinVal(l , r , 2*x+2 , md , rx);
  174.             if(p1.first == p2.first) return {p1.first , p1.second+p2.second};
  175.             else if(p1.first > p2.first) return p2;
  176.             else return p1;
  177.         }
  178.     }
  179.     pair<ll , int> getMinVal(int l , int r){
  180.         return getMinVal(l , r , 0 , 0 , size);
  181.     }
  182. };
  183. //======================================================
  184. ll gcd(ll a , ll b){
  185.     if(min(a,b) == 0) return max(a,b);
  186.     else return gcd(b , a%b);
  187. }
  188. //======================================================
  189. ll lcm(ll a , ll b){
  190.     return a / gcd(a,b) * b;
  191. }
  192. //======================================================
  193. ll KadaneMaxSum(vector<ll> &arr){
  194.     ll globalSum = arr[0];
  195.     ll curSum = arr[0];
  196.     int n = arr.size();
  197.     for(int i = 1 ; i < n ; i++){
  198.         curSum = max(arr[i] ,curSum+arr[i]);
  199.         globalSum = max(globalSum , curSum);
  200.     }
  201.     return globalSum;
  202. }
  203. //======================================================
  204. ll KadaneMinSum(vector<ll> &arr){
  205.     ll globalSum = arr[0];
  206.     ll curSum = arr[0];
  207.     int n = arr.size();
  208.     for(int i = 1 ; i < n ; i++){
  209.         curSum = min(arr[i] ,curSum+arr[i]);
  210.         globalSum = min(globalSum , curSum);
  211.     }
  212.     return globalSum;
  213. }
  214. //======================================================
  215. struct Sieve{
  216.     int N;
  217.     vector<int> primes;
  218.     vector<int> isPrime;
  219.     Sieve(int n){
  220.         N = n;
  221.         isPrime.resize(N+5);
  222.         for(int i = 0 ; i < N+5 ; i++)
  223.             isPrime[i] = true;
  224.         sieve();
  225.     }
  226.     bool check(int x){
  227.         return isPrime[x];
  228.     }
  229.     void sieve(){
  230.         isPrime[0] = isPrime[1] = false;
  231.         for(int i = 2 ; i*i < N ; i++){
  232.             if(isPrime[i])
  233.                 for(int j = i*i ; j< N ; j+=i){
  234.                     isPrime[j] = false;
  235.                 }
  236.  
  237.         }
  238.         for(int i = 2 ; i < N ; i++)
  239.             if(isPrime[i])
  240.                 primes.push_back(i);
  241.     }
  242. };
  243. //======================================================
  244. ll stringMod(string num , ll mod){
  245.     ll ans = 0;
  246.     int n = num.size();
  247.     for(int i = 0 ; i < n ; i++){
  248.         int d = num[i]-'0';
  249.         ans = (ans*10+d)%mod;
  250.     }
  251.     return ans;
  252. }
  253. //======================================================
  254. ll fp(ll base , ll pow , int cMod = MOD){
  255.     ll ans = 1;
  256.     while(pow){
  257.         if(pow&1) ans = (ans%cMod * base%cMod)%cMod;
  258.         base = (base*base)%cMod;
  259.         pow >>=1;
  260.     }
  261.     return ans;
  262. }
  263. //======================================================
  264. bool isPrime(ll n){ //not optimise
  265.     for(int i = 2 ; i*i<=n ; i++)
  266.         if(n%i == 0) return  false;
  267.     return  true;
  268. }
  269. //======================================================
  270. ll findXOR(ll n){
  271.     ll mod = n % 4;
  272.     if (mod == 0)
  273.         return n;
  274.     else if (mod == 1)
  275.         return 1;
  276.     else if (mod == 2)
  277.         return n + 1;
  278.     else if (mod == 3)
  279.         return 0;
  280. }
  281. //======================================================
  282. ll findXOR(ll l, ll r){
  283.     return (findXOR(l - 1) ^ findXOR(r));
  284. }
  285. //======================================================
  286. struct combinatorics{
  287.     vector<ll> fac;
  288.     vector<ll> invers;
  289.     combinatorics(){
  290.         fac.push_back(1);
  291.         invers.push_back(1);
  292.         for(int i = 1 ; i < 1e6 ; i++){
  293.             fac.push_back( (fac.back()*i)%MOD );
  294.             invers.push_back(fp(fac.back() , MOD-2)%MOD);
  295.         }
  296.     }
  297.     ll nCr(int n , int r){
  298.         return (fac[n]%MOD * invers[r]%MOD * invers[n-r]%MOD)%MOD;
  299.     }ll nPr(int n , int r){
  300.         return (fac[n]%MOD *  invers[n-r]%MOD)%MOD;
  301.     }
  302. };
  303. //======================================================
  304. vector<int> childCnt(N);
  305. int countChild(int root , int cnt ,vector<vector<int>> &adj, vector<bool> &vis){
  306.     vis[root] = true;
  307.     for(int num : adj[root])
  308.         if(!vis[num])
  309.             cnt += countChild(num,1 , adj , vis);
  310.     childCnt[root] = cnt-1;
  311.     return cnt;
  312. }
  313. //======================================================
  314. class comp{
  315. public:
  316.     bool operator()(pair<int , int> a , pair<int , int> b){
  317.         if(a.first != b.first) return a.first<b.first;
  318.         else return a.second>b.second;
  319.     }
  320. };
  321. //=====================================================
  322. int dijkstra(vector<vector<pair<int , int>>> &adj ,  ll u , ll v){
  323.     int oo = 1e7;
  324.     ll dic[adj.size()+5];
  325.     ll par[adj.size()+5];
  326.     for(ll i = 0 ; i < adj.size()+5 ; i++)
  327.         dic[i] = oo , par[i] = 0;;
  328.     priority_queue<pair<ll , ll> , vector<pair<ll , ll>> , greater<>> pq;
  329.     pq.push({0 , u});
  330.     dic[u] = 0;
  331.     while(!pq.empty()){
  332.         ll cost = pq.top().first;
  333.         ll node = pq.top().second;
  334.         pq.pop();
  335.         if(cost > dic[node]) continue;
  336.         for(auto child : adj[node]){
  337.             int nxtCost = child.second;
  338.             if(nxtCost + cost < dic[child.first]){
  339.                 dic[child.first] = nxtCost + cost;
  340.                 par[child.first] = node;
  341.                 pq.push({nxtCost + cost , child.first});
  342.             }
  343.         }
  344.     }
  345.     return dic[v];
  346. }
  347. //=====================================================
  348. bool bellman_ford(ll src ,ll n ,  vector<pair<pair<ll , ll> , ll>> &list){
  349.     ll dist[n+1];
  350.     ll oo = 1e9;
  351.     for(ll i = 1 ; i <= n ; i++ )
  352.         dist[i] = oo;
  353.     dist[src] = 0;
  354.     for(ll i = 1 ; i <= n ;i++){
  355.         for(ll j = 0 ; j < list.size() ; j++){
  356.             if(dist[list[j].first.first] + list[j].second < dist[list[j].first.second]){
  357.                 dist[list[j].first.second] = dist[list[j].first.first] + list[j].second;
  358.                 if(i == n) return true;
  359.             }
  360.         }
  361.     }
  362.     return false;
  363. }
  364. //=====================================================
  365. vector<vector<int>> floydList;
  366. void floyd_warshall(int n , vector<pair<pair<int , int> , int>> &list){
  367.     int oo = 1e8;
  368.     floydList.assign(n+1 , vector<int>(n+1 , oo));
  369.     for(int i = 1 ; i <= n ;i++)
  370.         floydList[i][i] = 0;
  371.     for(pair<pair<int , int> , int> p : list){
  372.         floydList[p.first.first][p.first.second] = p.second;
  373.         floydList[p.first.second][p.first.first] = p.second;
  374.     }
  375.     for(int k = 1 ; k <= n ; k++)
  376.         for(int i = 1 ; i <= n ; i++)
  377.             for(int j = 1 ; j <= n ; j++)
  378.                 floydList[i][j] = min(floydList[i][j] , floydList[i][k] + floydList[k][j]);
  379. }
  380. //=====================================================
  381. void File(){
  382. //    freopen("doroob.in", "r", stdin);
  383. //        freopen("output.txt", "w", stdout);
  384. }
  385. //=====================================================
  386. void testCase(ll ct){
  387.     ll n , m;
  388.     cin >> n >> m;
  389.     ll rx , ry , mx , my;
  390.     cin >> rx >> ry >> mx >> my;
  391.     if(rx > mx){
  392.         cout<<"-1\n";
  393.         return;
  394.     }
  395.     if(ry > my){
  396.         my = ry + (ry-my);
  397.     }
  398.     ll ans = 1e17;
  399.     ll st = 0 , en = 2e10;
  400.     while(st<=en){
  401.         ll md = st+en>>1;
  402.         ll tempx =rx+md, tempy=ry+md;
  403.         if(tempx > mx){
  404.             en = md-1;
  405.             continue;
  406.         }
  407.         if(tempy > m){
  408.             en = md-1;
  409.             continue;
  410.         }
  411.         if(tempy < my){
  412.             st = md+1;
  413.             continue;
  414.         }
  415.         ll dis = mx-tempx;
  416.         if(tempy-dis == my){
  417.             ans = min(ans,md+dis);
  418.             break;
  419.         }
  420.         else if(tempy-dis > my){
  421.             en = md-1;
  422.         }else{
  423.             st = md+1;
  424.         }
  425.     }
  426.     st = 0 , en = 2e10;
  427.     while(st<=en){
  428.         ll md = st+en>>1;
  429.         ll tempx =rx+md, tempy=ry-md;
  430.         if(tempx > mx){
  431.             en = md-1;
  432.             continue;
  433.         }
  434.         if(tempy <=0){
  435.             en = md-1;
  436.             continue;
  437.         }
  438.         if(tempy > my){
  439.             st = md+1;
  440.             continue;
  441.         }
  442.         ll dis = mx-tempx;
  443.         if(tempy+dis == my){
  444.             ans = min(ans,md+dis);
  445.             break;
  446.         }
  447.         else if(tempy+dis > my){
  448.             st = md+1;
  449.         }else{
  450.             en = md-1;
  451.         }
  452.     }
  453.  
  454.     if(ans == 1e17) ans = -1;
  455.     cout<<ans<<"\n";
  456. }
  457. int main(){
  458.     File();
  459.     FastCode();
  460.     int t = 1;
  461.     cin >> t;
  462.     for(int i = 1 ; i <= t ; i++)
  463.         testCase(i);
  464.     return 0;
  465. }
Success #stdin #stdout 0.01s 6996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/rrGHz9
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!