记录编号	590801	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	天天爱射击	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	22.993 s
提交时间	2024-07-11 16:53:44	内存使用	257.63 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
int l[205],r[205],s[205][MAXN],a[1005][MAXN];
int qs_l[MAXN],qs_r[MAXN],hrd[MAXN],ans[MAXN];
int n,m,len,idx=1,x[MAXN];
int main(){
    freopen("shooting.in","r",stdin);
    freopen("shooting.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>qs_l[i]>>qs_r[i]>>hrd[i];
    len=(m/200)+1;
    l[1]=1,r[1]=len;
    for(int i=1;i<=m;i++){
        if(i>r[idx]){
            l[++idx]=i,r[idx]=min(i+len-1,n);
        }
//        cout<<i<<" "<<idx<<endl;
        cin>>x[i];
        a[idx][x[i]]++;
    }
    for(int i=1;i<=idx;i++){
        for(int j=1;j<=200000;j++){
            s[i][j]=a[i][j]+s[i][j-1];
//            if(i==316)cout<<i<<" "<<j<<" "<<s[i][j]<<endl;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=idx;j++){
//            cout<<j<<" "<<hrd[i]<<" "<<qs_r[i]<<" "<<qs_l[i]<<" "<<s[j][qs_r[i]]<<" "<<s[j][qs_l[i]-1]<<" "<<s[j][qs_r[i]]-s[j][qs_l[i]-1]<<endl;
            if(hrd[i]>s[j][qs_r[i]]-s[j][qs_l[i]-1]){
                hrd[i]-=s[j][qs_r[i]]-s[j][qs_l[i]-1];
            }else{
//                cout<<i<<" "<<l[j]<<" "<<r[j]<<endl;
                for(int u=l[j];u<=r[j];u++){
                    if(x[u]>=qs_l[i]&&x[u]<=qs_r[i]){
                        hrd[i]--;
                        if(!hrd[i]){
                            ans[u]++;
                            break;
                        }
                    }
                }
                break;
            }
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
//    return cerr<<clock()<<"MS"<<endl,0;
      return 0;
}