[BZOJ1828][Usaco2010 Mar]balloc 农场分配

1828: [Usaco2010 Mar]balloc 农场分配

Time Limit: 3 Sec Memory Limit: 32 MB Submit: 678 Solved: 383 [Submit][Status][Discuss]

Description

Input

第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行：第i+N+1行表示2个整数 A_i和B_i

Output

* 第一行：一个整数表示最多能够被满足的要求数

Sample Input

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

Sample Output

将牛按右端点排序，每次能插入就插入，否则舍弃，线段树区间维护即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char buf[10000000], *ptr = buf - 1;
inline int readint(){
    int f = 1, n = 0;
    char ch = *++ptr;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = *++ptr;
    }
    while(ch <= '9' && ch >= '0'){
        n = (n << 1) + (n << 3) + ch - '0';
        ch = *++ptr;
    }
    return f * n;
}
const int maxn = 100000 + 10, INF = 0x3f3f3f3f;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
int tag[maxn << 2], mi[maxn << 2];
inline void PushUp(int rt){
    mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
void Build(int l, int r, int rt){
    tag[rt] = 0;
    if(l == r) mi[rt] = readint();
    else{
        int mid = l + r >> 1;
        Build(lson);
        Build(rson);
        PushUp(rt);
    }
}
inline void PushDown(int rt){
    if(tag[rt]){
        mi[rt << 1] -= tag[rt];
        mi[rt << 1 | 1] -= tag[rt];
        tag[rt << 1] += tag[rt];
        tag[rt << 1 | 1] += tag[rt];
        tag[rt] = 0;
    }
}
void Update(int ql, int qr, int l, int r, int rt){
    if(ql <= l && r <= qr){
        mi[rt]--;
        tag[rt]++;
    }
    else{
        PushDown(rt);
        int mid = l + r >> 1;
        if(ql <= mid) Update(ql, qr, lson);
        if(qr > mid) Update(ql, qr, rson);
        PushUp(rt);
    }
}
int Query(int ql, int qr, int l, int r, int rt){
    if(ql <= l && r <= qr) return mi[rt];
    else{
        PushDown(rt);
        int mid = l + r >> 1, ret = INF;
        if(ql <= mid) ret = min(ret, Query(ql, qr, lson));
        if(qr > mid) ret = min(ret, Query(ql, qr, rson));
        return ret;
    }
}
struct Node{
    int x, y;
    Node(){}
    bool operator < (const Node &a) const {
        return y < a.y;
    }
}a[maxn];
int main(){
    fread(buf, sizeof(char), sizeof(buf), stdin);
    int N, M;
    N = readint();
    M = readint();
    Build(1, N, 1);
    for(int i = 1; i <= M; i++){
        a[i].x = readint();
        a[i].y = readint();
    }
    sort(a + 1, a + M + 1);
    int ans = 0;
    for(int i = 1; i <= M; i++){
        if(Query(a[i].x, a[i].y, 1, N, 1)){
            ans++;
            Update(a[i].x, a[i].y, 1, N, 1);
        }
    }
    printf("%d
", ans);
    return 0;
}