记录编号	517596	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.008 s
提交时间	2018-10-27 19:48:15	内存使用	23.18 MiB

#include <cstdio>
#include <algorithm>
#include <cstring> 
#define N 1000005

using namespace std;

int n,m;
int r[N],d[N],s[N],t[N];
int c[N],sum[N];

inline int read(){
    int x = 0,k = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') k = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48),c = getchar();
    return x * k;
}

inline int judge(int x) {
    memset(c,0,sizeof(c));
    for(register int i = 1;i <= x; i++) {
        c[s[i]] += d[i];
        c[t[i] + 1] -= d[i];
    }
    for(register int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + c[i];
        if(sum[i] > r[i]) return 0;

    }
    return 1;
}

int main() {
	freopen("classrooms.in","r",stdin);
    freopen("classrooms.out","w",stdout);
    scanf("%d %d",&n, &m);
    for(register int i = 1; i <= n; i++) r[i] = read();
    for(register int i = 1; i <= m; i++){d[i] = read();s[i] = read();t[i] = read();} 
    if(judge(m)){printf("0\n"); return 0;}
    else printf("-1\n");
    int l = 1,r = m,mid;
    while(l < r) {
        mid = (l + r) >> 1;
        if(judge(mid)) l = mid + 1;
        else r = mid;
    }
    printf("%d\n",l);
    return 0;
}