学步园

题目大意：给你n个港口，每个港口都有个容量，然后有m条船要在s是进入sec，e时出去，问最多可以满足几条船的要求 n<=10 m<=100000 有多组数据

因为不同的港口互不影响，所以把不同的港口分开做

对于相同的港口，只要按出来的时间贪心就行了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=15,maxm=100010,maxt=maxm*4;
using namespace std;
 
#ifdef judgeonline
const int maxchar=5000000;
char buf[maxchar],*wbuf=buf;
inline int getint(){
    int tmp=0;
    while (*wbuf<'0' || *wbuf>'9') ++wbuf;
    for (;*wbuf>='0' && *wbuf<='9';++wbuf) tmp=tmp*10+*wbuf-'0';
    return tmp;
}
#else
 
inline int getint(){
    char ch=getchar(); int tmp=0;
    while (ch<'0' || ch>'9') ch=getchar();
    for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0';
    return tmp;
}
#endif
 
struct zy{
    int I,O,W;
}b[maxm];
 
inline bool cmp(zy a,zy b){
    return a.W<b.W;
}
 
 
inline bool cmp1(zy a,zy b){
    return a.O<b.O;
}
 
int n,m;
int a[maxn],l[maxn],r[maxn];
void init(){
    m=getint();
    for (int i=1;i<=n;++i)
        a[i]=getint();
    for (int i=1;i<=m;++i){
        b[i].I=getint()+1;
        b[i].O=getint()+1;
        b[i].W=getint();
    }
    sort(b+1,b+m+1,cmp);
    memset(l,63,sizeof(l));
    memset(r,200,sizeof(r));
    for (int i=1;i<=m;++i){
        l[b[i].W]=min(l[b[i].W],i);
        r[b[i].W]=max(r[b[i].W],i);
    }
}
 
class TTree{
    private:
        int tree[maxt],add[maxt];
        inline void updata(int p){
            tree[p]=min(tree[p*2],tree[p*2+1]);
        }
         
        void build(int p,int l,int r,int x){
            add[p]=0;
            if (l==r){
                tree[p]=x;
                return;
            }
            int mid=(l+r)/2;
            build(p*2,l,mid,x);
            build(p*2+1,mid+1,r,x);
            updata(p);
        }
         
        inline void pushdown(int p){
            if (!add[p]) return;
            int Ls=p<<1,Rs=Ls+1;
            add[Ls]+=add[p];
            add[Rs]+=add[p];
            tree[Ls]+=add[p];
            tree[Rs]+=add[p];
            add[p]=0;
        }
         
        bool count(int p,int l,int r,int fir,int las){
            if (l==fir && r==las) 
                return tree[p]>0;
            pushdown(p);
            int mid=(l+r)/2;
            if (mid>=las) return count(p*2,l,mid,fir,las);
            if (mid<fir) return count(p*2+1,mid+1,r,fir,las);
            return count(p*2,l,mid,fir,mid) && count(p*2+1,mid+1,r,mid+1,las);
        }
         
        void ins(int p,int l,int r,int fir,int las,int m){
            if (l==fir && r==las){
                tree[p]+=m;
                add[p]+=m;
                return;
            }
            int mid=(l+r)/2;
            if (mid>=las) 
                ins(p*2,l,mid,fir,las,m);
            else
            if (mid<fir)
                ins(p*2+1,mid+1,r,fir,las,m);
            else{
                ins(p*2,l,mid,fir,mid,m);
                ins(p*2+1,mid+1,r,mid+1,las,m);
            }
            updata(p);
        }
         
    zy tmp[maxm];
    public:
        int doit(int i,int l,int r){
            if (l>maxm) return 0;
            if (r<0) return 0;
            int maxT=0;
            memcpy(tmp+1,b+l,(r-l+1)*sizeof(zy));
            int n=r-l+1;
            sort(tmp+1,tmp+n+1,cmp1);
            maxT=tmp[n].O;
            build(1,1,maxT,a[i]);
            int ans=0;
            for (int i=1;i<=n;++i){
                if (tmp[i].I==tmp[i].O) ans++;
                else
                if (count(1,1,maxT,tmp[i].I,tmp[i].O-1)){
                    ans++;
                    ins(1,1,maxT,tmp[i].I,tmp[i].O-1,-1);
                }
            }
            return ans;
        }
}Tree;
 
void work(){
    int ans=0;
    for (int i=1;i<=n;++i)
        ans+=Tree.doit(i,l[i],r[i]);
    printf("%d\n",ans);
}
 
int main(){
    while (scanf("%d",&n)!=EOF){
        init();
        work();
    }
    return 0;
}