Two Array Problem
Problem Statement :
In this problem you operate on two arrays of integers. We will call them the and the respectively. Your goal is just to maintain them under the modification operations, such as: 1 : Reverse the subarray of the array, starting at the number, ending at the number, inclusively; 2 : Swap two consecutive fragments of the array, the first is from the number to the , the second is from the number to the ; 3 : Swap the piece that starts at the number and end at the one between the and the array; 4 : We consider only the piece from the number to the one. The numbers in the array are -coordinates of some set of points and the numbers in the array are -coordinates of them. For the obtained set of points we would like to place such a circle on a plane that would contain all the points in it and would have the minimal radius. Find this minimal radius. Input Format The first line of input contains two space separated integers and denoting the number of integers in arrays and the number of queries respectively. The second line contains space separated integers: the initial elements of the array. The third line contains space separated integers: the initial elements of the array. Then there are lines containing queries in the format listed above. Output Format For each type-4 query output the sought minimal radius with exactly two symbols after the decimal point precision. Constraints 1 <= N, M <= 10^5
Solution :
Solution in C :
In C++ :
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
void RI() {}
template<typename... T>
void RI( int& head, T&... tail ) {
scanf("%d",&head);
RI(tail...);
}
// }}}
const int INF=0x7FFFFFFF;
const int N=400010;
const double eps=1e-6;
struct P { double x,y; } p[N],q[3];
double dis2( P a, P b ) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); }
P operator -( P a, P b ) { return (P){a.x-b.x,a.y-b.y}; }
P operator +( P a, P b ) { return (P){a.x+b.x,a.y+b.y}; }
P operator /( P a, double b ) { return (P){a.x/b,a.y/b}; }
double abs2( P a ) { return a.x*a.x+a.y*a.y; }
double dot( P a, P b ) { return a.x*b.x+a.y*b.y; }
double X( P a, P b ) { return a.x*b.y-a.y*b.x; }
double X( P a, P b, P c ) { return X(b-a,c-a); }
struct C {
P o; double r2;
C() { o.x=o.y=r2=0; }
C( P a ) { o=a; r2=0; }
C( P a, P b ) { o=(a+b)/2; r2=dis2(o,a); }
C( P a, P b, P c ) {
double i,j,k,A=2*X(a,b,c)*X(a,b,c);
i=abs2(b-c)*dot(a-b,a-c);
j=abs2(a-c)*dot(b-a,b-c);
k=abs2(a-b)*dot(c-a,c-b);
o.x=(i*a.x+j*b.x+k*c.x)/A;
o.y=(i*a.y+j*b.y+k*c.y)/A;
r2=dis2(o,a);
}
bool cover( P a ) { return dis2(o,a)<=r2+eps; }
};
C MEC( int n, int m ) {
C mec;
if ( m==1 ) mec=C(q[0]);
else if ( m==2 ) mec=C(q[0],q[1]);
else if ( m==3 ) return C(q[0],q[1],q[2]);
for ( int i=0; i<n; i++ )
if ( !mec.cover(p[i]) ) {
q[m]=p[i];
mec=MEC(i,m+1);
}
return mec;
}
int my_rand() {
static int seed;
return seed=seed*1103515245+12345;
}
struct Treap {
static Treap mem[N],*pmem;
Treap *l,*r;
int rnd,size,val;
bool rev;
Treap() {}
Treap( int _val ):l(NULL),r(NULL),rnd(rand()),size(1),val(_val),rev(false) {}
} Treap::mem[N],*Treap::pmem=Treap::mem;
inline int size( Treap *t ) { return t?t->size:0; }
inline void push( Treap *t ) {
if ( !t ) return;
if ( t->rev ) {
if ( t->l ) t->l->rev^=1;
if ( t->r ) t->r->rev^=1;
swap(t->l,t->r);
t->rev=false;
}
}
inline void pull( Treap *t ) {
if ( !t ) return;
t->size=size(t->l)+size(t->r)+1;
}
Treap* merge( Treap *a, Treap *b ) {
if ( !a || !b ) return a?a:b;
if ( a->rnd < b->rnd ) {
push(a);
a->r=merge(a->r,b);
pull(a);
return a;
} else {
push(b);
b->l=merge(a,b->l);
pull(b);
return b;
}
}
void split( Treap *t, int k, Treap *&a, Treap *&b ) {
push(t);
if ( !t ) a=b=NULL;
else if ( k<=size(t->l) ) {
b=t;
split(t->l,k,a,b->l);
pull(b);
} else {
a=t;
split(t->r,k-size(t->l)-1,a->r,b);
pull(a);
}
}
void go( Treap *t, vector<int> &v ) {
if ( !t ) return;
push(t);
go(t->l,v);
v.PB(t->val);
go(t->r,v);
}
Treap* input( int n ) {
Treap *t=NULL;
REP1(i,1,n) {
int x;
RI(x);
t=merge(t,new (Treap::pmem++) Treap(x));
}
return t;
}
Treap *t[2];
int main() {
srand(time(0)^getpid()^514514514);
int n,m;
RI(n,m);
REP(i,2) t[i]=input(n);
while ( m-- ) {
int op;
RI(op);
if ( op==1 ) {
int id,l,r;
RI(id,l,r);
Treap *tl,*tr;
split(t[id],l-1,tl,t[id]);
split(t[id],r-l+1,t[id],tr);
t[id]->rev^=1;
t[id]=merge(merge(tl,t[id]),tr);
} else if ( op==2 ) {
int id,l1,r1,l2,r2;
RI(id,l1,r1,l2,r2);
Treap *t1,*t2,*t3,*t4,*t5;
split(t[id],l1-1,t1,t[id]);
split(t[id],r1-l1+1,t2,t[id]);
split(t[id],l2-r1-1,t3,t[id]);
split(t[id],r2-l2+1,t4,t5);
t[id]=merge(merge(merge(merge(t1,t4),t3),t2),t5);
} else if ( op==3 ) {
int l,r;
RI(l,r);
Treap *tl[2],*tm[2],*tr[2];
REP(i,2) {
split(t[i],l-1,tl[i],t[i]);
split(t[i],r-l+1,tm[i],tr[i]);
}
t[0]=merge(merge(tl[0],tm[1]),tr[0]);
t[1]=merge(merge(tl[1],tm[0]),tr[1]);
} else if ( op==4 ) {
int l,r;
RI(l,r);
vector<int> v[2];
REP(i,2) {
Treap *tl,*tr;
split(t[i],l-1,tl,t[i]);
split(t[i],r-l+1,t[i],tr);
go(t[i],v[i]);
t[i]=merge(merge(tl,t[i]),tr);
}
assert(v[0].size() == v[1].size());
int vn=SZ(v[0]);
REP(i,vn) {
p[i].x=v[0][i];
p[i].y=v[1][i];
}
random_shuffle(p,p+vn);
C c=MEC(vn,0);
double ans=sqrt(c.r2);
printf("%.2f\n",ans);
}
}
return 0;
}
In Java :
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Random;
import java.util.StringTokenizer;
public class TwoArrayProblem {
static int MAX = 1111111;
static class Node {
Node child[] = new Node[2], parent;
boolean reverse;
int value, size;
}
static class SplayTree {
public static final Node nil;
static {
nil = new Node();
nil.child[0] = nil.child[1] = nil.parent = nil;
nil.reverse = false;
nil.value = nil.size = 0;
}
private Node root = nil;
public SplayTree(int a[]) {
root = buildTree(a, 0, a.length - 1);
}
private Node buildTree(int a[], int l, int r) {
if (l > r) return nil;
int mid = (l + r) >> 1;
Node x = new Node();
x.value = a[mid];
x.parent = nil;
x.reverse = false;
setLink(x, buildTree(a, l, mid - 1), 0);
setLink(x, buildTree(a, mid + 1, r), 1);
update(x);
return x;
}
private void update(Node x) {
x.size = x.child[0].size + x.child[1].size + 1;
}
private void pushDown(Node x) {
if (x != nil) {
if (x.reverse) {
Node tmp = x.child[0];
x.child[0] = x.child[1];
x.child[1] = tmp;
x.reverse = false;
x.child[0].reverse = !x.child[0].reverse;
x.child[1].reverse = !x.child[1].reverse;
}
}
}
private static void setLink(Node parent,
Node child, int d) {
parent.child[d] = child;
child.parent = parent;
}
private int getDir(Node parent, Node child) {
return parent.child[0] == child ? 0 : 1;
}
private void rotate(Node x, int d) {
Node y = x.child[d], z = x.parent;
setLink(x, y.child[d ^ 1], d);
setLink(y, x, d ^ 1);
setLink(z, y, getDir(z, x));
update(x);
update(y);
}
private void splay(Node x) {
while (x.parent != nil) {
Node y = x.parent, z = y.parent;
int dy = getDir(y, x), dz = getDir(z, y);
if (z == nil) rotate(y, dy);
else if (dy == dz) {
rotate(z, dz);
rotate(y, dy);
} else {
rotate(y, dy);
rotate(z, dz);
}
}
root = x;
}
public void reverse(int right) {
if (right <= 1) return;
if (right == root.size) root.reverse = !root.reverse;
else {
accessByPos(right + 1);
root.child[0].reverse = !root.child[0].reverse;
}
}
public void reverse(int left, int right) {
if (left >= right) return;
reverse(right);
reverse(right - left + 1);
reverse(right);
}
public void swap(int left1, int right1,
int left2, int right2) {
reverse(left1, right1);
reverse(left2, right2);
reverse(right1 + 1, left2 - 1);
reverse(left1, right2);
}
private void dfs(Node root, int[] buffer) {
if (root == nil) return;
pushDown(root);
dfs(root.child[0], buffer);
buffer[++buffer[0]] = root.value;
dfs(root.child[1], buffer);
}
public void collect(int left, int right, int[] buffer) {
buffer[0] = 0;
if (left == 1 && right == root.size) {
dfs(root, buffer);
} else {
reverse(right);
Node x = accessByPos(right - left + 2).child[0];
dfs(x, buffer);
reverse(right);
}
}
public Node accessByPos(int pos) {
assert (pos >= 1 && pos <= root.size);
Node x = root;
pushDown(x);
while (x.child[0].size + 1 != pos) {
if (pos < x.child[0].size + 1) x = x.child[0];
else {
pos -= x.child[0].size + 1;
x = x.child[1];
}
pushDown(x);
}
splay(x);
return x;
}
}
static int n, m;
static int[] a;
static int[] buffer2 = new int[MAX];
static int[] buffer1 = new int[MAX];
static Random rand = new Random();
static double[][] p = new double[MAX][2];
static final double eps = 1E-8;
static double dis(double[] a, double[] b) {
return Math.sqrt((a[0] - b[0]) * (
a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
static void circumcenter(double[] a,
double[] b, double[] c, double[] res) {
double a1 = b[0] - a[0], b1 = b[1] - a[1],
c1 = (a1 * a1 + b1 * b1) / 2;
double a2 = c[0] - a[0], b2 = c[1] - a[1],
c2 = (a2 * a2 + b2 * b2) / 2;
double d = a1 * b2 - a2 * b1;
res[0] = a[0] + (c1 * b2 - c2 * b1) / d;
res[1] = a[1] + (a1 * c2 - a2 * c1) / d;
}
static double minDisk(int[] x, int[] y) {
// randomly permute them
for (int n = x[0]; n >= 1; n--) {
int i = rand.nextInt(n) + 1;
int tmp = x[i];
x[i] = x[n];
x[n] = tmp;
tmp = y[i];
y[i] = y[n];
y[n] = tmp;
}
for (int i = 1; i <= x[0]; i++) {
p[i][0] = x[i];
p[i][1] = y[i];
}
double[] c = p[1].clone();
double r = 0;
for (int i = 2; i <= x[0]; i++) {
if (dis(p[i], c) > r + eps) // ????
{
c[0] = p[i][0];
c[1] = p[i][1];
r = 0;
for (int j = 1; j < i; j++)
if (dis(p[j], c) > r + eps) // ????
{
c[0] = (p[i][0] + p[j][0]) / 2;
c[1] = (p[i][1] + p[j][1]) / 2;
r = dis(p[j], c);
for (int k = 1; k < j; k++)
if (dis(p[k], c) > r + eps) // ????
{// ?????????????
circumcenter(p[i], p[j], p[k], c);
r = dis(p[i], c);
}
}
}
}
return r;
}
public static void main(String[] args)
throws Exception {
BufferedReader cin = new BufferedReader(
new InputStreamReader(System.in));
BufferedWriter cout = new BufferedWriter(
new OutputStreamWriter(System.out));
StringTokenizer token =
new StringTokenizer(cin.readLine());
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
a = new int[2 * n];
int index = 0;
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
SplayTree tree = new SplayTree(a);
for (; m > 0; m--) {
token = new StringTokenizer(cin.readLine());
int op = Integer.parseInt(token.nextToken());
if (op == 1) {
int id = Integer.parseInt(token.nextToken());
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
if (id == 1) {
left += n;
right += n;
}
tree.reverse(left, right);
} else if (op == 2) {
int id = Integer.parseInt(token.nextToken());
int left1 = Integer.parseInt(token.nextToken());
int right1 = Integer.parseInt(token.nextToken());
int left2 = Integer.parseInt(token.nextToken());
int right2 = Integer.parseInt(token.nextToken());
if (id == 1) {
left1 += n;
right1 += n;
left2 += n;
right2 += n;
}
tree.swap(left1, right1, left2, right2);
} else if (op == 3) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.swap(left, right, left + n, right + n);
} else if (op == 4) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.collect(left, right, buffer1);
tree.collect(left + n, right + n, buffer2);
double r = minDisk(buffer1, buffer2);
cout.write(String.format("%.2f%n", r));
}
}
cin.close();
cout.close();
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct _ct_node{
int size;
int priority;
int value;
int reverse;
struct _ct_node *left,*right;
} ct_node;
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By);
double get_r(int x1,int y1,int x2,int y2,int x3,int y3);
int inside(int x,int y);
void sed(int idx,int r_size,int x1,int x2,
int x3,int y1,int y2,int y3);
double solve();
void tra(ct_node *root,int *A);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void push(ct_node *root);
ct_node* reverse(int A,int B,ct_node *root);
void computeTree();
int get_size(ct_node *root);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,
int*left_b,int*right_b,int left_size, int right_size);
int P[100000],st[100000],T[100000],a[100000],
b[100000],h1[100000],h2[100000],N,NN;
double pi,CX,CY,R;
ct_node poll[200000],*root[2];
int main(){
int M,x,l1,l2,r1,r2,i;
ct_node *p1,*p2,*p3,*p4,*p5,*p6;
pi=atan(1)*4;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++){
scanf("%d",&poll[i].value);
poll[i].priority=P[i]=rand();
poll[i].reverse=0;
poll[i].left=poll[i].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[0]=&poll[i];
else
if(i<T[i])
poll[T[i]].left=&poll[i];
else
poll[T[i]].right=&poll[i];
get_size(root[0]);
for(i=0;i<N;i++){
scanf("%d",&poll[i+N].value);
poll[i+N].priority=P[i]=rand();
poll[i+N].reverse=0;
poll[i+N].left=poll[i+N].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[1]=&poll[i+N];
else
if(i<T[i])
poll[T[i]+N].left=&poll[i+N];
else
poll[T[i]+N].right=&poll[i+N];
get_size(root[1]);
while(M--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d%d",&x,&l1,&r1);
root[x]=reverse(l1-1,r1-1,root[x]);
break;
case 2:
scanf("%d%d%d%d%d",&x,&l1,&r1,&l2,&r2);
split(r2-1,&p4,&p5,root[x]);
split(l2-2,&p3,&p4,p4);
split(r1-1,&p2,&p3,p3);
split(l1-2,&p1,&p2,p2);
root[x]=merge(merge(p1,p4),merge(p3,merge(p2,p5)));
break;
case 3:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
root[0]=merge(merge(p1,p5),p3);
root[1]=merge(merge(p4,p2),p6);
break;
default:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
NN=0;
tra(p2,a);
NN=0;
tra(p5,b);
root[0]=merge(merge(p1,p2),p3);
root[1]=merge(merge(p4,p5),p6);
printf("%.2lf\n",solve());
break;
}
}
return 0;
}
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By){
return (Ax-Ox)*(By-Oy)-(Ay-Oy)*(Bx-Ox);
}
double get_r(int x1,int y1,int x2,
int y2,int x3,int y3){
int minx,maxx;
double s2,s3,mx2,my2,mx3,my3;
mx2=((double)(x2+x1))/2;
my2=((double)(y2+y1))/2;
mx3=((double)(x3+x1))/2;
my3=((double)(y3+y1))/2;
if(y1==y2 && y1==y3){
CY=y1;
minx=x1;
if(x2<minx)
minx=x2;
if(x3<minx)
minx=x3;
maxx=x1;
if(x2>maxx)
maxx=x2;
if(x3>maxx)
maxx=x3;
CX=((double)(minx+maxx))/2;
return ((double)(maxx-minx))/2;
}
if(y1==y2){
s3=(x1-x3)/(double)(y3-y1);
CX=mx2;
CY=s3*CX-s3*mx3+my3;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
if(y1==y3){
s2=(x1-x2)/(double)(y2-y1);
CX=mx3;
CY=s2*CX-s2*mx2+my2;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
s2=(x1-x2)/(double)(y2-y1);
s3=(x1-x3)/(double)(y3-y1);
if(s2==s3)
return 0;
CX=(mx2*s2-mx3*s3-my2+my3)/(s2-s3);
CY=(my3*s2-my2*s3+s2*s3*mx2-s2*s3*mx3)/(s2-s3);
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
int inside(int x,int y){
return sqrt((x-CX)*(x-CX)+(y-CY)*(y-CY))<=R;
}
void sed(int idx,int r_size,int x1,
int x2,int x3,int y1,int y2,int y3){
if(idx==NN || r_size==3){
if(r_size<=1){
R=0;
CX=x1;
CY=y1;
}
else if(r_size==2){
R=sqrt((x2-x1)*(double)(x2-x1)+(y2-y1)*(
double)(y2-y1))/2;
CX=((double)(x1+x2))/2;
CY=((double)(y1+y2))/2;
}
else
R=get_r(x1,y1,x2,y2,x3,y3);
return;
}
sed(idx+1,r_size,x1,x2,x3,y1,y2,y3);
if(!inside(h1[idx],h2[idx]))
switch(r_size){
case 0:
sed(idx+1,r_size+1,h1[idx],x2,x3,h2[idx],y2,y3);
break;
case 1:
sed(idx+1,r_size+1,x1,h1[idx],x3,y1,h2[idx],y3);
break;
default:
sed(idx+1,r_size+1,x1,x2,h1[idx],y1,y2,h2[idx]);
}
return;
}
double solve(){
int n=NN,k=0,t,i,j;
sort_a2(a,b,NN);
for(i=0;i<n;i++){
while(k>=2 && cross(h1[k-2],h2[k-2],h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
for(i=n-2,t=k+1;i>=0;i--){
while(k>=t && cross(h1[k-2],h2[k-2],
h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
k--;
if(k<=1)
return 0;
if(k==2)
return sqrt((h1[0]-h1[1])*(
double)(h1[0]-h1[1])+(h2[0]-h2[1])*
(double)(h2[0]-h2[1]))/2;
for(i=0;i<k;i++){
j=rand()%(k-i)+i;
t=h1[i];
h1[i]=h1[j];
h1[j]=t;
t=h2[i];
h2[i]=h2[j];
h2[j]=t;
}
NN=k;
sed(0,0,0,0,0,0,0,0);
return R;
}
void tra(ct_node *root,int *A){
if(!root)
return;
push(root);
tra(root->left,A);
A[NN++]=root->value;
tra(root->right,A);
return;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
L->right=merge(L->right,R);
recalc(L);
return L;
}
push(R);
R->left=merge(L,R->left);
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x){
split(x-curIndex-1,&t,R,root->right);
root->right=t;
recalc(root);
*L=root;
}
else{
split(x,L,&t,root->left);
root->left=t;
recalc(root);
*R=root;
}
return;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}
ct_node* reverse(int A,int B,ct_node *root){
ct_node *l,*m,*r;
split(A-1,&l,&r,root);
split(B-A,&m,&r,r);
m->reverse^=1;
return merge(merge(l,m),r);
}
void computeTree(){
int i,k,top=-1;
for(i=0;i<N;i++){
k=top;
while(k>=0 && P[st[k]]<P[i])
k--;
if(k!=-1)
T[i]=st[k];
if(k<top)
T[st[k+1]]=i;
st[++k]=i;
top=k;
}
T[st[0]]=-1;
return;
}
int get_size(ct_node *root){
if(!root)
return 0;
root->size=get_size(root->left)+get_size(root->right)+1;
return root->size;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,
int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i] < right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
View More Similar Problems
Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →Counting On a Tree
Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n
View Solution →