HackerRank Quadrant Queries Problem Solution Yashwant Parihar, May 22, 2023May 28, 2024 In this post, we will solve HackerRank Quadrant Queries Problem Solution. There are n points on a plane. Each point p[i] is described by [x[i], y[i]], where 1 ≤ i ≤n. There are three types of queries needed: X i j Reflect all points in the inclusive range between points p[i] and p[j] along the x- axis. Yij Reflect all points in the inclusive range between points p[i] and pl] along the y-axis. Cij Count the number of points in the inclusive range between points p[i] and p[j] in each of the 4 quadrants. Then print a single line of four space-separated integers describing the respective numbers of points in the first, second, third, and fourth quadrants in that order Given a set of n points and q queries, perform each query in order. For example, given points p = [(1, 1), (-1,-1)] andqueries = [‘X 1 2’, ‘C 1 2’, ‘Y 1 1 C 1 2’]. Initially the points are in quadrants 1 and 3. The first query says to reflect points with indices from 1 to 2 along the -axis. After the query, p = [(1,-1), (-1, 1)] and quadrants are 4 and 2. The next query prints the number of points in each quadrant: 0 1 0 1. The third query says to reflect the point with index 1 to 1 along the y-axis, so now p= [(-1,-1), (-1, 1)]. The points now lie in quadrants 3 and 2, so the fourth query output is @ 1 1 0.Note: Points may sometimes share the same coordinates.Function DescriptionComplete the quadrants function in the editor below. It should print the results of each C type query on a new line.quadrants has the following parameters: p[p[1]…p[n]]; a 2-dimensional array of integers where each element p[i] contains twointegers [1] and y[i] queries[queries[1]…queries[n]: an array of strings Input FormatThe first line contains a single integer, n, that denotes the number of points.Each line i of the n subsequent lines contains two space-separated integers that describe the respective [2] and y[i] values for point p[i].The next line contains a single integer, q, that denotes the number of queries.Each of the a subsequent lines contains three space-separated values that describe a query in one of the three forms defined above. Output Format For each query of type C i j, print four space-separated integers that describe the number of points having indices in the inclusive range between i and j in the first, second, third, and fourth graph quadrants in that order. Sample Input 4 1 1 -1 1 -1 -1 1 -1 5 C 1 4 X 2 4 C 3 4 Y 1 2 C 1 3 Sample Output 1 1 1 1 1 1 0 0 0 2 0 1 ExplanationInitially, p = [[1, 1], -1, 1, -1, -1], [1, 1]] so there is one point in each of the four quadrants. The first query results in printing 1 1 1 1.The second query, X 2 4, reflects the points in the inclusive range between indices 2 and 4 along the x-axis. Now p = [[1,1],-1,-1], [1, 1], [1, 1]].The query C 3 4 requires that the number of points considering p[3] through p[4] be printed: 1 1 0 0The third query, Y 1 2 requires reflection of p[1]p[2] along the y-axis. Now p = [[1, 1], [1, 1], [−1, 1], [1, 1]].The last query, C 1 3 requires that the number of points considering p[1] through p[3] be printed: 0 2 0 1 HackerRank Quadrant Queries Problem Solution Quadrant Queries C Solution #include<stdio.h> #define g getchar_unlocked() struct abc { int f,s,t,ft; }; typedef struct abc abc; abc st[500004]={0}; int x[100002],y[100002]; char ii[500004][2]={0}; update(int node,int beg,int end,int i,int j,int type) { int mid,nnode,temp; if(i>end || j<beg) return; if(i<=beg && end<=j) { if(type==1) { ii[node][0]=1-ii[node][0]; st[node].f=(st[node].f+st[node].ft)-(st[node].ft=st[node].f); st[node].s=(st[node].s+st[node].t)-(st[node].t=st[node].s); return(0); } else { ii[node][1]=1-ii[node][1]; st[node].f=(st[node].f+st[node].s)-(st[node].s=st[node].f); st[node].t=(st[node].t+st[node].ft)-(st[node].ft=st[node].t); return(0); } } mid=(beg+end)/2; nnode=(node)<<1; update(nnode,beg,mid,i,j,type); update(nnode+1,mid+1,end,i,j,type); st[node].f=st[nnode].f+st[nnode+1].f; st[node].s=st[nnode].s+st[nnode+1].s; st[node].t=st[nnode].t+st[nnode+1].t; st[node].ft=st[nnode].ft+st[nnode+1].ft; if(ii[node][0]==1) { st[node].f=(st[node].f+st[node].ft)-(st[node].ft=st[node].f); st[node].s=(st[node].s+st[node].t)-(st[node].t=st[node].s); } if(ii[node][1]==1) { st[node].f=(st[node].f+st[node].s)-(st[node].s=st[node].f); st[node].t=(st[node].t+st[node].ft)-(st[node].ft=st[node].t); } return(0); } abc query(int node,int beg,int end,int xt,int yt,int i,int j) { int mid,nnode,t1,t2; abc ans={0}; if(i>end || j<beg) return(ans); if(i<=beg && end<=j) { abc ans=st[node]; if(xt==1) { ans.f=(ans.f+ans.ft)-(ans.ft=ans.f); ans.s=(ans.s+ans.t)-(ans.t=ans.s); } if(yt==1) { ans.f=(ans.f+ans.s)-(ans.s=ans.f); ans.t=(ans.t+ans.ft)-(ans.ft=ans.t); } return(ans); } abc ans1,ans2; mid=(beg+end)/2; nnode=2*node; t1=(xt+ii[node][0])%2; t2=(yt+ii[node][1])%2; ans1=query(nnode,beg,mid,t1,t2,i,j); ans2=query(nnode+1,mid+1,end,t1,t2,i,j); ans1.f+=ans2.f;ans1.s+=ans2.s;ans1.t+=ans2.t;ans1.ft+=ans2.ft; return(ans1); } init(int node,int beg,int end) { int nnode,mid; if(beg==end) { if(x[beg]>0) { if(y[beg]>0) (st[node].f)++; else (st[node].ft)++; } else { if(y[beg]>0) (st[node].s)++; else (st[node].t)++; } return; } nnode=(node)<<1; mid=(beg+end)/2; init(nnode,beg,mid); init(nnode+1,mid+1,end); st[node].f=st[nnode].f+st[nnode+1].f; st[node].s=st[nnode].s+st[nnode+1].s; st[node].t=st[nnode].t+st[nnode+1].t; st[node].ft=st[nnode].ft+st[nnode+1].ft; return(0); } scan() { int t=0,m=1; char c; c=g; while((c<'0' || c>'9') && c!='-') c=g; if(c=='-') { m=-1; c=g; } while(c>='0' && c<='9') { t=(t<<3)+(t<<1)+c-'0'; c=g; } return(t*m); } int main() { int n,q,a,b,i; char tp; abc ans; n=scan(); for(i=0;i<n;i++) {x[i]=scan();y[i]=scan();} init(1,0,n-1); q=scan(); while(q--) { tp=getchar();a=scan();b=scan(); if(tp=='X') update(1,0,n-1,a-1,b-1,1); else if(tp=='Y') update(1,0,n-1,a-1,b-1,2); else { ans=query(1,0,n-1,0,0,a-1,b-1); printf("%d %d %d %d\n",ans.f,ans.s,ans.t,ans.ft); } } return(0); } Quadrant Queries C++ Solution #include <bits/stdc++.h> using namespace std; int N, Q; int X[100010]; int Y[100010]; int L, R; char type; struct Node { int count[4] = {0}; int x_flip = 0; int y_flip = 0; Node() {} Node(int a, int b, int c, int d) { count[0] = a; count[1] = b; count[2] = c; count[3] = d; } void FlipX() { swap(count[0], count[3]); swap(count[1], count[2]); } void FlipY() { swap(count[0], count[1]); swap(count[2], count[3]); } }; Node tree[1000010]; Node GetNode(int x, int y) { Node res; if(y > 0) { res.count[(x < 0)]++; } else { res.count[2 + (x > 0)]++; } return res; } Node Combine(Node a, Node b) { Node res; for(int i = 0; i < 4; i++) { res.count[i] = a.count[i] + b.count[i]; } return res; } Node Reflect(Node node) { Node res; vector<pair<int, int>> indices = (type == 'X') ? vector<pair<int, int>>({{0, 3}, {1, 2}, {2, 1}, {3, 0}}) : vector<pair<int, int>>({{0, 1}, {1, 0}, {2, 3}, {3, 2}}); for(auto it : indices) { res.count[it.first] = node.count[it.second]; } return res; } void Reflect(int node, int low, int high, int L, int R) { if(low > high || high < L || low > R) { return; } // if(low == high) if(low >= L && high <= R) { // tree[node] = Reflect(tree[node]); tree[node].x_flip ^= (type == 'X'); tree[node].y_flip ^= (type == 'Y'); if(type == 'X') tree[node].FlipX(); if(type == 'Y') tree[node].FlipY(); return; } int mid = (low + high) / 2; Reflect(node * 2 + 1, low, mid, L, R); Reflect(node * 2 + 2, mid + 1, high, L, R); int x_flip = tree[node].x_flip; int y_flip = tree[node].y_flip; tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]); tree[node].x_flip = x_flip; tree[node].y_flip = y_flip; // if(type == 'X') tree[node].FlipX(); // if(type == 'Y') tree[node].FlipY(); if(tree[node].x_flip) tree[node].FlipX(); if(tree[node].y_flip) tree[node].FlipY(); } void Build(int node, int low, int high) { if(low == high) { tree[node] = GetNode(X[low], Y[low]); return; } int mid = (low + high) / 2; Build(node * 2 + 1, low, mid); Build(node * 2 + 2, mid + 1, high); tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]); } Node Count(int node, int low, int high, int L, int R, int flip_x = 0, int flip_y = 0) { if(low > high || high < L || low > R) { return Node(0,0,0,0); } if(low >= L && high <= R) { auto res = tree[node]; if(flip_x) res.FlipX(); if(flip_y) res.FlipY(); return res; } int mid = (low + high) / 2; // if(R <= mid) // { // return Count(node * 2 + 1, low, mid, L, R); // } // else if(L > mid) // { // return Count(node * 2 + 2, mid + 1, high, L, R); // } // Node a = Count(node * 2 + 1, low, mid, L, min(R, mid)); // Node b = Count(node * 2 + 2, mid + 1, high, max(mid + 1, L), R); flip_x ^= tree[node].x_flip; flip_y ^= tree[node].y_flip; Node a = Count(node * 2 + 1, low, mid, L, R, flip_x, flip_y); Node b = Count(node * 2 + 2, mid + 1, high, L, R, flip_x, flip_y); return Combine(a, b); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i = 0; i < N; i++) { cin >> X[i] >> Y[i]; } Build(0, 0, N - 1); cin >> Q; for(int i = 0; i < Q; i++) { cin >> type >> L >> R; L--; R--; switch(type) { case 'X': { Reflect(0, 0, N - 1, L, R); break; } case 'Y': { Reflect(0, 0, N - 1, L, R); break; } case 'C': { Node ans = Count(0, 0, N - 1, L, R); for(int i = 0; i < 4; i++) { cout << ans.count[i] << " "; } cout << "\n"; break; } } } return 0; } Quadrant Queries C Sharp Solution using System; using System.Collections.Generic; using System.IO; namespace Algorithms.hackerrank { public class Solution { private enum Quadrant { First = 0, Second, Third, Forth } private enum QueryType { X = 0, // reflection about x-axis Y, // reflection about y-axis, XY, None, C } private sealed class Segment { public QueryType Type { get; set; } public int Start { get; private set; } public int End { get; private set; } private int[] count = new int[4]; private static QueryType[,] tb = new QueryType[4, 4]; public int[] Count { get { return this.count; } } public Segment(int start, int end) { this.Start = start; this.End = end; this.Type = QueryType.None; } public int this[int i] { get { return count[i]; } set { count[i] = value; } } private void Swap(Quadrant i, Quadrant j) { int x = count[(int)i]; count[(int)i] = count[(int)j]; count[(int)j] = x; } public void Transform() { switch (Type) { case QueryType.X: Swap(Quadrant.First, Quadrant.Forth); Swap(Quadrant.Second, Quadrant.Third); break; case QueryType.Y: Swap(Quadrant.First, Quadrant.Second); Swap(Quadrant.Third, Quadrant.Forth); break; case QueryType.XY: Swap(Quadrant.First, Quadrant.Third); Swap(Quadrant.Second, Quadrant.Forth); break; } Type = QueryType.None; } static Segment() { for (QueryType t1 = QueryType.X; t1 <= QueryType.None; t1++) { for (QueryType t2 = QueryType.X; t2 <= QueryType.None; t2++) { tb[(int)t1, (int)t2] = Transform(t1, t2); } } } public void Transform(QueryType type) { Type = tb[(int)type, (int)Type]; } private static QueryType Transform(QueryType t1, QueryType t2) { if (t1 == QueryType.X) { switch (t2) { case QueryType.X: return QueryType.None; case QueryType.Y: return QueryType.XY; case QueryType.XY: return QueryType.Y; case QueryType.None: return QueryType.X; } } else if (t1 == QueryType.Y) { switch (t2) { case QueryType.X: return QueryType.XY; case QueryType.Y: return QueryType.None; case QueryType.XY: return QueryType.X; case QueryType.None: return QueryType.Y; } } else if (t1 == QueryType.XY) { switch (t2) { case QueryType.X: return QueryType.Y; case QueryType.Y: return QueryType.X; case QueryType.XY: return QueryType.None; case QueryType.None: return QueryType.XY; } } return t2; } public override string ToString() { return string.Format("{0} - {1} : {2} {3} {4} {5} : {6}", Start, End, count[0], count[1], count[2], count[3], Type); } } private sealed class SegmentTree { public delegate void Count(int[] count, int index); private Segment[] segments; private Count fn; public SegmentTree(int N, Count fn) { segments = new Segment[270000]; // for this particular question, it can't go beyond this size this.fn = fn; Initialize(0, 1, N); } private void Initialize(int index, int start, int end) { Segment seg = new Segment(start, end); segments[index] = seg; if (start == end) { fn(seg.Count, start); return; } int leftIdx = GetLeftChildIndex(index); int rightIdx = GetRightChildIndex(index); Initialize(leftIdx, start, (start + end) / 2); Initialize(rightIdx, (start + end) / 2 + 1, end); Segment left = segments[leftIdx]; Segment right = segments[rightIdx]; for (int i = 0; i < 4; i++) { seg[i] = left[i] + right[i]; } } public void Update(int start, int end, QueryType type) { Update(0, start, end, type); } private void Update(int index, int start, int end, QueryType type) { var seg = segments[index]; if (seg.Start == seg.End) { // elementary segment, at leaf seg.Transform(type); seg.Transform(); return; } int leftIdx = GetLeftChildIndex(index); int rightIdx = GetRightChildIndex(index); var left = segments[leftIdx]; var right = segments[rightIdx]; if (seg.Start == start && seg.End == end) { // current segment covers the exact range, stops here, push update to both children seg.Transform(type); left.Transform(seg.Type); right.Transform(seg.Type); seg.Transform(); return; } // propagate the transformation to both children left.Transform(seg.Type); right.Transform(seg.Type); seg.Type = QueryType.None; if (start <= left.End) { Update(leftIdx, start, Math.Min(end, left.End), type); } else { Update(leftIdx, left.Start, left.End, QueryType.None); } if (end >= right.Start) { Update(rightIdx, Math.Max(start, right.Start), end, type); } else { Update(rightIdx, right.Start, right.End, QueryType.None); } for (int i = 0; i < 4; i++) { seg[i] = left[i] + right[i]; } } public int[] Query(int start, int end) { int[] count = new int[4]; Query(0, start, end, count); return count; } private void Query(int index, int start, int end, int[] count) { Segment seg = segments[index]; if (seg.Type != QueryType.None) { Update(index, start, end, QueryType.None); } if (seg.Start == start && seg.End == end) { for (int i = 0; i < 4; i++) { count[i] += seg[i]; } return; } int leftIdx = GetLeftChildIndex(index); int rightIdx = GetRightChildIndex(index); var left = segments[leftIdx]; var right = segments[rightIdx]; if (start <= left.End) Query(leftIdx, start, Math.Min(end, left.End), count); if (end >= right.Start) Query(rightIdx, Math.Max(start, right.Start), end, count); } private int GetRightChildIndex(int i) { return 2 * i + 1; } private int GetLeftChildIndex(int i) { return 2 * i + 2; } } private Quadrant FindQuadrant(int x, int y) { if (x > 0 && y > 0) return Quadrant.First; if (x < 0 && y < 0) return Quadrant.Third; if (x > 0) return Quadrant.Forth; return Quadrant.Second; } private void Solve(int start, int end, QueryType type) { if (type == QueryType.C) { int[] count = tree.Query(start, end); Console.WriteLine(string.Format("{0} {1} {2} {3}", count[0], count[1], count[2], count[3])); } else { tree.Update(start, end, type); } } private void Count(int[] count, int index) { string[] ln = rd.ReadLine().Split(' '); Quadrant q = FindQuadrant(int.Parse(ln[0]), int.Parse(ln[1])); count[(int)q] = 1; } private TextReader rd; private SegmentTree tree; private int N = 0; private void Run(TextReader rd) { N = int.Parse(rd.ReadLine()); this.rd = rd; tree = new SegmentTree(N, Count); int Q = int.Parse(rd.ReadLine()); for (; Q > 0; Q--) { string[] ln = rd.ReadLine().Split(' '); var t = ln[0]; QueryType type = QueryType.C; if (t == "X") type = QueryType.X; else if (t == "Y") type = QueryType.Y; Solve(int.Parse(ln[1]), int.Parse(ln[2]), type); } //Console.ReadKey(); } public static void Main(string[] args) { TextReader rd = Console.In; if (args.Length != 0) rd = new StreamReader(new FileStream(args[0], FileMode.Open, FileAccess.Read)); new Solution().Run(rd); } } } Quadrant Queries Java Solution /* Enter your code here. Read input from STDIN. Print output to STDOUT */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; public class Solution { private static final int[] BC = new int[1<<16]; public static void main(String[] argv) throws Exception { prep(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line1 = br.readLine(); int N = Integer.parseInt(line1); ArrayList<String> dump = new ArrayList<String>(100000); int[] x = new int[N/32+1]; int[] y = new int[N/32+1]; long rs = System.currentTimeMillis(); for(int i=0;i<N;i++){ String line2 = br.readLine(); String[] tmp2 = line2.split(" "); if(tmp2[0].charAt(0) != '-') x[i/32] |= 1<< i%32; if(tmp2[1].charAt(0) != '-') y[i/32] |= 1<< i%32; } long re = System.currentTimeMillis(); String line3 = br.readLine(); int Q = Integer.parseInt(line3); boolean wasC = false; int[] tmp1 = new int[N/32+1]; int[] tmp24= new int[N/32+1]; int[] tmp2 = new int[N/32+1]; int[] cnt1 = new int[N/32+1]; int[] cnt24= new int[N/32+1]; int[] cnt2 = new int[N/32+1]; long ws = System.currentTimeMillis(); for(int i=0;i<Q;i++){ String line4 = br.readLine(); String[] tmp4 = line4.split(" "); int sindex = Integer.parseInt(tmp4[1]); int eindex = Integer.parseInt(tmp4[2]); int sm = (sindex-1)%32; int sn = (sindex-1)/32; int em = eindex%32; int en = eindex/32; int es = eindex-sindex+1; if(tmp4[0].equals("X")) { if(sn == en){ int mask = ((1<<(es))-1)<<(sm); y[en] ^= mask; }else{ int mask = -1; int fmask = mask<<(sm); int emask = (1<<(em))-1; y[sn] ^= fmask; for(int j=sn+1;j<en;j++) y[j] ^= mask; y[en] ^= emask; } wasC = false; }else if(tmp4[0].equals("Y")) { if(sn == en){ int mask = ((1<<(es))-1)<<(sm); x[en] ^= mask; }else{ int mask = -1; int fmask = mask<<(sm); int emask = (1<<(em))-1; x[sn] ^= fmask; for(int j=sn+1;j<en;j++) x[j] ^= mask; x[en] ^= emask; } wasC = false; }else{ /* if(!wasC || wasC){ for(int j=0;j<x.length;j++) { tmp1[j] = x[j] & y[j]; tmp24[j] = x[j] ^ y[j]; tmp2[j] = tmp24[j] & y[j]; cnt1[j] = bitCount(tmp1[j]); cnt24[j]= bitCount(tmp24[j]); cnt2[j] = bitCount(tmp2[j]); } } */ int maskes = ((1<<(es))-1)<<(sm); int maskall = -1; int fmask = maskall<<(sm); int emask = (1<<(em))-1; // 1st quadrant x bit: 1, y bit: 1 (x & y) int c1 = 0; if(sn == en){ c1 += bitCount(x[en] & y[en] & maskes); }else{ c1 += bitCount(x[sn] & y[sn] & fmask); for(int j=sn+1;j<en;j++) c1 += bitCount(x[j] & y[j]); c1 += bitCount(x[en] & y[en] & emask); } // 2nd quadrant x bit: 0, y bit: 1 // 4th quadrant x bit: 1, y bit: 0 // x xor y = c2 + c4 // (x xor y) & y = c2 int c24 = 0; int c2 = 0; if(sn == en){ int t2 = (x[en] ^ y[en]) & maskes; c24 += bitCount(t2); c2 += bitCount(t2 & y[en]); }else{ int t2 = (x[sn] ^ y[sn]) & fmask; c24 += bitCount(t2); c2 += bitCount(t2 & y[sn]); for(int j=sn+1;j<en;j++) { t2 = x[j] ^ y[j]; c24 += bitCount(t2); c2 += bitCount(t2 & y[j]); } t2 = (x[en] ^ y[en]) & emask; c24 += bitCount(t2); c2 += bitCount(t2 & y[en]); } int c4 = c24 - c2; // 3rd quadrant x bit: 0, y bit: 0 (total - c1 - c2 - c4) int c3 = eindex - sindex + 1 - c1 - c2 - c4; dump.add(c1+" "+c2+" "+c3+" "+c4); //System.out.println(c1+" "+c2+" "+c3+" "+c4); wasC = true; } } long we = System.currentTimeMillis(); for(int i=0;i<dump.size();i++) System.out.println(dump.get(i)); br.close(); //System.out.println("R:"+(re-rs)); //System.out.println("W:"+(we-ws)); } private static void prep() { int max = 1<<16; int step1 = 1<<8; for(int i=0;i<step1;i++) BC[i] = Integer.bitCount(i); for(int i=step1;i<max;i++){ BC[i] = BC[i&0xFF] + BC[(i>>8)&0xFF]; } } private static int bitCount(int i){ return BC[i&0xFFFF] + BC[(i>>16)&0xFFFF]; } } Quadrant Queries JavaScript Solution 'use strict'; var SZ = 30; var MASK = 0; for (var i = 0, j = 1; i < SZ; i++, j *= 2) { MASK |= j; } function Quadrant(N) { this.N = N; this.len = Math.floor(N / SZ) + ((N % SZ == 0) ? 0 : 1); this.quadrants0 = new Array(this.len); this.quadrants1 = new Array(this.len); this.quadrants2 = new Array(this.len); this.quadrants3 = new Array(this.len); this.counts0 = new Array(this.len); this.counts1 = new Array(this.len); this.counts2 = new Array(this.len); this.counts3 = new Array(this.len); for (var i = 0; i < this.len; i++) { this.quadrants0[i] = 0; this.quadrants1[i] = 0; this.quadrants2[i] = 0; this.quadrants3[i] = 0; this.counts0[i] = 0; this.counts1[i] = 0; this.counts2[i] = 0; this.counts3[i] = 0; } this.iMasks = []; this.jMasks = []; for (var k = 0; k < SZ; k++) { this.iMasks[k] = this.getMask(k, SZ - 1); // (MASK >> (SZ - (i % SZ))) ^ MASK this.jMasks[k] = this.getMask(0, k); // (MASK >> (SZ - 1 - (j % SZ))) } } Quadrant.prototype.init = function(points) { for (var i = 0; i < this.N; i++) { var d = Math.floor(i / SZ); var bit = 1 << (i % SZ); var pt = points[i]; var x = pt[0]; var y = pt[1] var q = ( ((x >= 0 && y >= 0) ? 0 : 0) + ((x < 0 && y >= 0) ? 1 : 0) + ((x < 0 && y < 0) ? 2 : 0) + ((x >= 0 && y < 0) ? 3 : 0) ); if (q == 0) { this.quadrants0[d] |= bit; this.counts0[d]++; } else if (q == 1) { this.quadrants1[d] |= bit; this.counts1[d]++; } else if (q == 2) { this.quadrants2[d] |= bit; this.counts2[d]++; } else if (q == 3) { this.quadrants3[d] |= bit; this.counts3[d]++; } else {} } }; Quadrant.prototype.recount = function(idx) { var q0 = this.quadrants0[idx]; var q1 = this.quadrants1[idx]; var q2 = this.quadrants2[idx]; var q3 = this.quadrants3[idx]; var count0 = 0; var count1 = 0; var count2 = 0; var count3 = 0; while (q0 > 0) { if (q0 & 1) { count0++; } q0 >>= 1; } while (q1 > 0) { if (q1 & 1) { count1++; } q1 >>= 1; } while (q2 > 0) { if (q2 & 1) { count2++; } q2 >>= 1; } while (q3 > 0) { if (q3 & 1) { count3++; } q3 >>= 1; } this.counts0[idx] = count0; this.counts1[idx] = count1; this.counts2[idx] = count2; this.counts3[idx] = count3; } Quadrant.prototype.maskSwapY = function(idx, mask) { var q0 = this.quadrants0[idx] & mask; var q1 = this.quadrants1[idx] & mask; var q2 = this.quadrants2[idx] & mask; var q3 = this.quadrants3[idx] & mask; this.quadrants0[idx] ^= q0; this.quadrants1[idx] ^= q1; this.quadrants2[idx] ^= q2; this.quadrants3[idx] ^= q3; this.quadrants0[idx] |= q3; this.quadrants1[idx] |= q2; this.quadrants2[idx] |= q1; this.quadrants3[idx] |= q0; this.recount(idx); } Quadrant.prototype.getMask = function(i, j) { return (MASK >> (SZ - (i % SZ))) ^ (MASK >> (SZ - 1 - (j % SZ))); }; Quadrant.prototype.maskSwapX = function(idx, mask) { var q0 = this.quadrants0[idx] & mask; var q1 = this.quadrants1[idx] & mask; var q2 = this.quadrants2[idx] & mask; var q3 = this.quadrants3[idx] & mask; this.quadrants0[idx] ^= q0; this.quadrants1[idx] ^= q1; this.quadrants2[idx] ^= q2; this.quadrants3[idx] ^= q3; this.quadrants0[idx] |= q1; this.quadrants1[idx] |= q0; this.quadrants2[idx] |= q3; this.quadrants3[idx] |= q2; this.recount(idx); }; Quadrant.prototype.swapY = function(i, j) { var i0 = Math.floor(i / SZ); var j0 = Math.floor(j / SZ); var i1 = i0 + ((i % SZ != 0) ? 1 : 0); var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0); if (i0 == j0) { this.maskSwapY(i0, this.getMask(i, j)); return; } if (i0 < i1) { this.maskSwapY(i0, this.iMasks[i % SZ]); } if (j0 > j1) { this.maskSwapY(j0, this.jMasks[j % SZ]); } for (var idx = i1; idx <= j1; idx++) { var q0 = this.quadrants0[idx]; var q1 = this.quadrants1[idx]; var q2 = this.quadrants2[idx]; var q3 = this.quadrants3[idx]; this.quadrants0[idx] = q3; this.quadrants1[idx] = q2; this.quadrants2[idx] = q1; this.quadrants3[idx] = q0; var c0 = this.counts0[idx]; var c1 = this.counts1[idx]; var c2 = this.counts2[idx]; var c3 = this.counts3[idx]; this.counts0[idx] = c3; this.counts1[idx] = c2; this.counts2[idx] = c1; this.counts3[idx] = c0; } } Quadrant.prototype.swapX = function(i, j) { var i0 = Math.floor(i / SZ); var j0 = Math.floor(j / SZ); var i1 = i0 + ((i % SZ != 0) ? 1 : 0); var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0); if (i0 == j0) { this.maskSwapX(i0, this.getMask(i, j)); return; } if (i0 < i1) { this.maskSwapX(i0, this.iMasks[i % SZ]); } if (j0 > j1) { this.maskSwapX(j0, this.jMasks[j % SZ]); } for (var idx = i1; idx <= j1; idx++) { var q0 = this.quadrants0[idx]; var q1 = this.quadrants1[idx]; var q2 = this.quadrants2[idx]; var q3 = this.quadrants3[idx]; this.quadrants0[idx] = q1; this.quadrants1[idx] = q0; this.quadrants2[idx] = q3; this.quadrants3[idx] = q2; var c0 = this.counts0[idx]; var c1 = this.counts1[idx]; var c2 = this.counts2[idx]; var c3 = this.counts3[idx]; this.counts0[idx] = c1; this.counts1[idx] = c0; this.counts2[idx] = c3; this.counts3[idx] = c2; } } Quadrant.prototype.maskCount = function(idx, mask) { var c0 = 0, c1 = 0, c2 = 0, c3 = 0; var q0 = this.quadrants0[idx] & mask; var q1 = this.quadrants1[idx] & mask; var q2 = this.quadrants2[idx] & mask; var q3 = this.quadrants3[idx] & mask; while (q0 > 0) { if (q0 & 1) { c0++; } q0 >>= 1; } while (q1 > 0) { if (q1 & 1) { c1++; } q1 >>= 1; } while (q2 > 0) { if (q2 & 1) { c2++; } q2 >>= 1; } while (q3 > 0) { if (q3 & 1) { c3++; } q3 >>= 1; } return [c0, c1, c2, c3]; }; Quadrant.prototype.count = function(i, j) { var i0 = Math.floor(i / SZ); var j0 = Math.floor(j / SZ); var i1 = i0 + ((i % SZ != 0) ? 1 : 0); var j1 = j0 - ((((j + 1) % SZ) != 0) ? 1 : 0); var count0 = 0, count1 = 0, count2 = 0, count3 = 0; if (i0 == j0) { var a = this.maskCount(i0, this.getMask(i, j)); count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3]; return (count0 + ' ' + count1 + ' ' + count2 + ' ' + count3); } if (i0 < i1) { var a = this.maskCount(i0, this.iMasks[i % SZ]); count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3]; } if (j0 > j1) { var a = this.maskCount(j0, this.jMasks[j % SZ]); count0 += a[0]; count1 += a[1]; count2 += a[2]; count3 += a[3]; } for (var k = i1; k <= j1; k++) { count0 += this.counts0[k]; count1 += this.counts1[k]; count2 += this.counts2[k]; count3 += this.counts3[k]; } return (count0 + ' ' + count1 + ' ' + count2 + ' ' + count3); } function processData(input) { var parse_fun = function (s) { return parseInt(s, 10); }; var lines = input.split('\n'); var N = parse_fun(lines.shift()); var points = lines.splice(0, N).map(function (s) { return s.split(' ').map(parse_fun); }); var quadrant = new Quadrant(N); quadrant.init(points); var Q = parse_fun(lines.shift()); var queries = lines.splice(0, Q); var res = []; for (var q = 0; q < Q; q++) { var params = queries[q].split(' '); var op = params[0]; var i = parse_fun(params[1]) - 1; var j = parse_fun(params[2]) - 1; if (op == 'X') { quadrant.swapY(i, j); } else if (op == 'Y') { quadrant.swapX(i, j); } else if (op == 'C') { res.push(quadrant.count(i, j)); } else {} } process.stdout.write(res.join('\n')); } process.stdin.resume(); process.stdin.setEncoding("ascii"); var _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); }); Quadrant Queries Python Solution #!/usr/env python import bisect from math import sqrt import optparse import sys from random import randint as rand _Rx = [3, 2, 1, 0] _Ry = [1, 0, 3, 2] def create_test(N, Q, fp): r = [(rand(-2, 2), rand(-2, 2)) for i in range(N)] print(N, file = fp) for ri in r: print('%d %d' % ri, file = fp) ops = [ "X", "Y", "C" ] queries = [(ops[rand(0, 2)], rand(1, N), rand(1, N)) for q in range(Q)] print(Q, file = fp) for op, i, j in queries: if i > j: i, j = j, i print('%1s %d %d' % (op, i, j), file = fp) return [r, queries] def quadrant(x, y): ''' Return the quadrant the point r is in. ''' if x > 0: if y > 0: return 0 else: return 3 else: if y > 0: return 1 else: return 2 def getInput(f, shift = -1): ''' The first line contains N, the number of points. N lines follow. The ith line contains xi and yi separated by a space. The next line contains Q the number of queries. The next Q lines contain one query each, of one of the above forms. All indices are 1 indexed. Return the points r and the queries q, in [r, q] ''' l = f.readline().strip() n = int(l) r = [] for i in range(n): l = f.readline().strip() x, y = l.split() r.append([int(x), int(y)]) l = f.readline().strip() Q = int(l) queries = [] for k in range(Q): l = f.readline().strip() op, i, j = l.split() queries.append((op, int(i) + shift, int(j) + shift)) return [r, queries] class QuadrantBook: ''' A data structure to facilitate the processing of quadrant queries. ''' def __init__(self, r, factor = 32): N = len(r) self.blocksize = int(sqrt(factor * N)) nblocks = (N - 1) // self.blocksize + 1 # self.inq[b][q] is the list of points in the quadrant q with indices # between b L and (b+1)L, where L is the blocksize. self.inq = [[[] for q in range(4) ] for b in range(nblocks)] for i, ri in enumerate(r): b = self.getBlock(i) q = quadrant(ri[0], ri[1]) self.inq[b][q].append(i) def countInQuadrants( self, i, j): ''' Count the number of points in each quadrant with indices between i and j, inclusive. ''' bi = self.getBlock(i) bj = self.getBlock(j) cq = [0] * 4 if bi == bj: for q, idx in enumerate(self.inq[bi]): ki, kj = getIndex(idx, i, j) cq[q] = kj - ki return cq else: for q in range(4): ni = self.inq[bi][q] nj = self.inq[bj][q] ki = bisect.bisect_left(ni, i) kj = bisect.bisect_right(nj, j) cq[q] = len(ni) - ki for nb in self.inq[bi + 1: bj]: cq[q] += len(nb[q]) cq[q] += kj return cq def reflect( self, i, j, axis): ''' Update the list of points in each quadrant after reflection along the given axis. ''' if axis == "X": R = _Rx W = [(0, 3), (1, 2)] else: R = _Ry W = [(0, 1), (2, 3)] bi = self.getBlock( i) bj = self.getBlock( j) if bi == bj: self.reflectInBlock( i, j, bi, R) else: ni = self.inq[bi] kiq = [bisect.bisect_left(idx, i) for idx in ni] rfxi = [ni[q][ki:] for q, ki in enumerate(kiq)] for q, ki in enumerate(kiq): ni[q] = ni[q][:ki] + rfxi[R[q]] nj = self.inq[bj] kjq = [bisect.bisect_right( idx, j) for idx in nj] rfxj = [nj[q][:kj] for q, kj in enumerate(kjq)] for q, kj in enumerate( kjq): nj[q] = rfxj[R[q]] + nj[q][kj:] for nb in self.inq[bi + 1: bj]: for w1, w2 in W: nb[w1], nb[w2] = nb[w2], nb[w1] def getBlock( self, i ): ''' Get the block index for point i. ''' return i // self.blocksize def reflectInBlock(self, i, j, b, R): ''' Update the list of points in each quadrant after reflection along the given axis, assuming that i and j are in the same block b. ''' nb = self.inq[b] kij = [getIndex( idx, i, j) for idx in nb] rf = [nb[q][ki: kj] for q, (ki, kj) in enumerate(kij)] for q, (ki, kj) in enumerate(kij): nb[q] = nb[q][:ki] + rf[R[q]] + nb[q][kj:] def getIndex( lst, i, j): ''' In the sorted list, find ki such that lst[ki-1]<i<=lst[ki], and kj such that lst[kj]<=j<lst[kj+1]. If i<lst[0], ki=0; if j>lst[-1], kj=len(lst). This convention splices the list at the right places. @param i<=j ''' ki = bisect.bisect_left(lst, i) kj = bisect.bisect_right(lst, j, ki) return [ki, kj] def processQueries(r, queries, factor = 32): qbook = QuadrantBook(r, factor) for op, i, j in queries: if op.upper() == 'C': cq = qbook.countInQuadrants(i, j) print('%d %d %d %d' % tuple(cq), file = sys.stdout) elif op.upper() in ['X', 'Y']: qbook.reflect( i, j, op) if __name__ == '__main__': usage = '%prog' opt = optparse.OptionParser(usage) opt.add_option('-N', type = 'int', default = 100) opt.add_option('-Q', type = 'int', default = 10) opt.add_option('-c', '--create', action = 'store_true', default = False, help = 'Create test case instead of running the query.') opt.add_option('-i', '--input', type='string', default = None, help = 'Input file.') opt.add_option('-b', '--block-factor', type = 'float', default = 32., help = 'Use sqrt(b * N) as the block size.') opts, args = opt.parse_args() if opts.create: r, queries = create_test(opts.N, opts.Q, sys.stdout) else: r, queries = getInput(opts.input and open(opts.input, 'r') or sys.stdin) processQueries(r, queries, opts.block_factor) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython