Untitled

//khoi tao n passenger, M ng/khoang , diem, jobid
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#define maxM 10001
#define maxN 100001
#define maxK 11
using namespace std;
int K;
struct node 
{
	int id;
	int score;
	int job;
	int idHi;
	int idLo;
	int carNum;
};

node p[maxN];
struct pHi
{
    int buffer[maxM * 2];
    int count;
 
 
    void clear()
    {
        count = 0;        
    }
 
	int cmp(int u, int v)
	{
		if(p[buffer[u]].score > p[buffer[v]].score)return 1;
		if(p[buffer[u]].score == p[buffer[v]].score && p[buffer[u]].id < p[buffer[v]].id) return 1;
		return -1;
	}
    /*int cmp(int a, int b)
    {
        int c = p[buffer[a]].score - p[buffer[b]].score;
        if (c == 0) {
            return  p[buffer[b]].id - p[buffer[a]].id;
        }
        return c; 
    }*/
 
 
    void swap(int a, int b)
    {
        int temp = buffer[a];
        buffer[a] = buffer[b];
        buffer[b] = temp;
 
 
        p[buffer[a]].idHi = a;
        p[buffer[b]].idHi = b;
    }
 
 
    void push(int id) {
        buffer[++count] = id;
        p[id].idHi = count;
        up(count);
    }
 
 
    void pop() {
        swap(1, count);
        p[buffer[count]].idHi = 0;
        count--;
        down(1);
    }
 
 
    void pop(int loc) {
        swap(loc, count);
        int cmpValue = cmp(loc, count);
        p[buffer[count]].idHi = 0;
        count--;
        if (cmpValue < 0) {
            down(loc);
        }
        else if (cmpValue > 0) {
            up(loc);
        }
    }
 
 
    int top() {
        return buffer[1];
    }
 
 
    void up(int loc) {
        int par = loc /2 ;
        while (par >= 1) {
            if (cmp(par, loc) > 0) break;
            swap(par, loc);
            loc = par;
            par = loc /2;
        }
    }
 
 
    void down(int loc) {
        int son = loc*2;
        while (son <= count) {
            if (son < count) {
                if (cmp(son + 1, son) > 0) son = son + 1;
            }
            if (cmp(loc, son) >= 0) break;
            swap(loc, son);
            loc = son;
            son = loc*2;
        }
    }
 
 
};

struct pLo
{
    int buffer[maxM * 2];
    int count;
 
 
    void clear()
    {
        count = 0;        
    }
 
 
    int cmp(int a, int b)
    {
        int c = p[buffer[b]].score - p[buffer[a]].score;
        if (c == 0) {
            return  p[buffer[a]].id - p[buffer[b]].id;
        }
        return c; 
    }
 
 
    void swap(int a, int b)
    {
        int temp = buffer[a];
        buffer[a] = buffer[b];
        buffer[b] = temp;
 
 
        p[buffer[a]].idLo = a;
        p[buffer[b]].idLo = b;
    }
 
 
    void push(int id) {
        buffer[++count] = id;
        p[id].idLo = count;
        up(count);
    }
 
 
    void pop() {
        swap(1, count);
        p[buffer[count]].idLo = 0;
        count--;
        down(1);
    }
 
 
    void pop(int loc) {
        swap(loc, count);
        int cmpValue = cmp(loc, count);
        p[buffer[count]].idLo = 0;
        count--;
        if (cmpValue < 0) {
            down(loc);
        }
        else if (cmpValue > 0) {
            up(loc);
        }
    }
 
 
    int top() {
        return buffer[1];
    }
 
 
    void up(int loc) {
        int par = loc /2;
        while (par >= 1) {
            if (cmp(par, loc) > 0) break;
            swap(par, loc);
            loc = par;
            par = loc /2;
        }
    }
 
 
    void down(int loc) {
        int son = loc * 2;
        while (son <= count) {
            if (son < count) {
                if (cmp(son + 1, son) > 0) son = son + 1;
            }
            if (cmp(loc, son) >= 0) break;
            swap(loc, son);
            loc = son;
            son = loc * 2 ;
        }
    }
 
 
};

 pHi heapHi[maxK];
 pLo heapLow[maxK];
 
 
//int JCount[MAX_JOB];
int JobGroup[1001][201];
 
 
 
 
void Pop(int k, int passId)
{
    heapHi[k].pop(p[passId].idHi);
    heapLow[k].pop(p[passId].idLo);
}
 
 
void Push(int k, int passId)
{
    p[passId].carNum = k;
 
 
    heapHi[k].push(passId);
    heapLow[k].push(passId);    
}
 
void init(int N, int M, int J, int mPoint[], int mJobID[])
{
	K= N/M;
	//cout<<N<<" "<<M<<" "<<K<<" "<<J<<"\n";
	
	for(int i=0;i<N/M;i++)
		{
			heapLow[i].clear();
			heapHi[i].clear();
			
	}
	for(int i=0;i<=J;i++)JobGroup[i][0]=0;
	for(int i = 0; i< N; i++)
	{
		int k = i/M;
		p[i].id = i;
		p[i].score = mPoint[i];
		p[i].job = mJobID[i];
		p[i].carNum = k;
		Push(k,i);
		JobGroup[mJobID[i]][++JobGroup[mJobID[i]][0]]= i;
	}

}

void destroy()
{

}
// sưa diểm của ng mID mPoint
int update(int mID, int mPoint)
{
	node *newNode = &p[mID];
	newNode->score += mPoint;
	int k = newNode->carNum;
	if(mPoint >0)
	{
		heapHi[k].up(newNode->idHi);
		heapLow[k].down(newNode->idLo);
	}else
	{
		heapHi[k].down(newNode->idHi);
		heapLow[k].up(newNode->idLo);
	}
	//cout<<mID<<" thanh "<<newNode->score<<"\n";
	return newNode->score;
}
// update by Job
int updateByJob(int mJobID, int mPoint)
{
	//cout<<"Job "<<mJobID<<" "<<JobGroup[mJobID][0]<<" \n";
	int ans=0;
	for(int i=1;i<=JobGroup[mJobID][0];i++)
	{
		int mID = JobGroup[mJobID][i];
		node *newNode = &p[mID];
		newNode->score += mPoint;
		int k = newNode->carNum;
		if(mPoint >0)
		{
		heapHi[k].up(newNode->idHi);
		heapLow[k].down(newNode->idLo);
		}else
		{
		heapHi[k].down(newNode->idHi);
		heapLow[k].up(newNode->idLo);
		}
		ans += newNode->score;
	}
	
	return ans;
	return -1;
}
// di chuyen nNum ng điểm thấp của toa trc sang toa sau, nNum ng điểm cao của toa sau lên toa trc
//diem thap thi lay ID cao, diem cao thi lay ID thap
int sau[11][6];
int truoc[11][6];
int move(int mNum)
{	
	int ans=0;
	int k=K;
	for(int i=0;i<K-1;i++)
	{
		for(int j=1;j<=mNum;j++)
		{
			int u=heapLow[i].top();
			sau[i][j]=u;
			Pop(i,u);
			//cout<<u<<" - "<<p[u].score<<"\n";
			ans+= p[u].score;
		}
		
		for(int j=1;j<=mNum;j++)
		{
			int u=heapHi[i+1].top();
			truoc[i+1][j]=u;
			Pop(i+1,u);
			//cout<<u<<" - "<<p[u].score<<"\n";
			ans+= p[u].score;
		}
		//cout<<"\n";
	}

	for(int i=0;i<K-1;i++)
	{
		for(int j=1;j<=mNum;j++)
			{
				Push(i,truoc[i+1][j]);
				//cout<<i<<" + "<<truoc[i+1][j]<<"\n";
				Push(i+1,sau[i][j]);
				//cout<<i+1<<" + "<<sau[i][j]<<"\n";
			}

	}

//	for(int i=0;i<K;i++)heapHi[i].inAll();
	//cout<<ans<<"\n";
	return ans;
}