刚开始用线段树。。。。TLE了。。。。
但是学长用线段树优化,过了,感觉好厉害。
感觉题解的想法。。。。为什么自己想不到呢。。。感觉好巧。
#include <stdio.h> #include <string.h> #define maxn 100010 #define ll __int64 ll a[maxn]; int main() { ll num; while(scanf("%I64d",&num)!=EOF&&num) { memset(a,0,sizeof(a)); ll n,m; ll sum=0; scanf("%I64d",&n); ll i,j; ll x,y,z; for(i=0;i<n;i++) { scanf("%I64d%I64d%I64d",&x,&y,&z); a[x]+=z; a[y+1]-=z; } for(i=1;i<=num;i++) { a[i]+=a[i-1]; // printf("***%d",a[i]); } // printf("\n"); for(i=num-1;i>=1;i--) { a[i]+=a[i+1]; // printf("%d***",a[i]); } // printf("\n"); scanf("%I64d",&m); for(i=0;i<m;i++) { scanf("%I64d%I64d",&x,&y); if(x>a[y]) sum++; } printf("%I64d\n",sum); } return 0; }