# USACO[Elite 2010 March Competition/gold]balloc

CODE:

/*

PROG: balloc

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-27

DESCRIPTION:

TITLE: Barn Allocation [Jaehyun Park/Jeffrey Wang, 2010]

CONTENT:

Farmer John recently opened up a new barn and is now accepting stall

allocation requests from the cows since some of the stalls have a

better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered

1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i

may request a contiguous interval of stalls (A_i, B_i) in which to

roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to

wander among all the stalls in the range A_i..B_i (and the stalls

must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum

number of them that can be satisfied without exceeding stall

capacities.

Consider both a barn with 5 stalls that have the capacities shown

and a set cow requests:

Stall id:    1   2   3   4   5

+—+—+—+—+—+

Capacity:  | 1 | 3 | 2 | 1 | 3 |

+—+—+—+—+—+

Cow 1       XXXXXXXXXXX             (1, 3)

Cow 2           XXXXXXXXXXXXXXX     (2, 5)

Cow 3           XXXXXXX             (2, 3)

Cow 4                   XXXXXXX     (4, 5)

FJ can’t satisfy all four cows, since there are too many requests

for stalls 3 and 4.

Noting that Cow 2 requests an interval that includes stalls 3 and

4, we test the hypothesis that cows 1, 3, and 4 can have their

requested stalls. No capacity is exceeded, so the answer for this

set of data is 3 — three cows (1, 3, and 4) can have their requests

satisfied.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

PROBLEM NAME: balloc

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..N+M+1: Line i+N+1 contains two integers: A_i and B_i

SAMPLE INPUT (file balloc.in):

5 4

1

3

2

1

3

1 3

2 5

2 3

4 5

OUTPUT FORMAT:

* Line 1: The maximum number of requests that can be satisfied

SAMPLE OUTPUT (file balloc.out):

3

*/

#include <stdio.h>

#define MAXN 100000

#define MAXM 100000

#define oo ~(1<<31)

int N,M;

int C[MAXN+1];

int A[MAXM],B[MAXM];

int st_min[MAXN<<2],st_cnt[MAXN<<2];

void quick_sort(int L,int R)

{

int mid_A=A[(L+R)>>1];

int mid_B=B[(L+R)>>1];

int i=L,j=R;

while (i<=j)

{

while (A[i]<mid_A||(A[i]==mid_A&&B[i]>mid_B)) i++;

while (A[j]>mid_A||(A[j]==mid_A&&B[j]<mid_B)) j–;

if (i<=j)

{

int swap;

swap=A[i];

A[i]=A[j];

A[j]=swap;

swap=B[i];

B[i]=B[j];

B[j]=swap;

i++;

j–;

}

}

if (L<j) quick_sort(L,j);

if (i<R) quick_sort(i,R);

}

int min(int a,int b)

{

return a<b?a:b;

}

void build(int L,int R,int root=1)

{

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

if (L==R) st_min[root]=C[L];

else

{

build(LL,LR,Lroot);

build(RL,RR,Rroot);

st_min[root]=min(st_min[Lroot],st_min[Rroot]);

}

//printf(“[%d,%d] min:%d\n”,L,R,st_min[root]);

}

void update(int L,int R,int root)

{

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

st_cnt[Lroot]+=st_cnt[root];

st_min[Lroot]-=st_cnt[root];

st_cnt[Rroot]+=st_cnt[root];

st_min[Rroot]-=st_cnt[root];

st_cnt[root]=0;

}

int ask(int l,int r,int L,int R,int root=1)

{

if (l>R||r<L) return oo;

if (l<=L&&R<=r) return st_min[root];

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

update(L,R,root);

}

void insert(int l,int r,int L,int R,int inc=1,int root=1)

{

if (l>R||r<L) return;

if (l<=L&&R<=r)

{

st_cnt[root]+=inc;

st_min[root]-=inc;

return;

}

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

update(L,R,root);

insert(l,r,LL,LR,inc,Lroot);

insert(l,r,RL,RR,inc,Rroot);

st_min[root]=min(st_min[Lroot],st_min[Rroot]);

}

int main()

{

freopen(“balloc.in”,“r”,stdin);

freopen(“balloc.out”,“w”,stdout);

scanf(“%d %d\n”,&N,&M);

for (int i=1;i<=N;i++)

scanf(“%d\n”,&C[i]);

for (int i=0;i<M;i++)

scanf(“%d %d\n”,&A[i],&B[i]);

build(1,N);

quick_sort(0,M-1);

for (int i=M-1;i>=0;i–)

fclose(stdin);

fclose(stdout);

return 0;

}