记录编号	590786	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	天天爱射击	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	25.778 s
提交时间	2024-07-11 15:30:24	内存使用	7.90 MiB

#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

int n, m;
struct node
{
    int l;
    int r;
    int s;
};
vector<node> q(200005);

vector<int> z(200005);
vector<int> zt(200005);
int blog[200005];
int L[505];
int R[505];
int ans[200005];
int num;

inline void build()
{
    int block = sqrt(m*log2(m));
    num = m/block;
    if(m%block) num++;
    for(ll i = 1; i <= num; ++i)
    {
        L[i] = (i-1)*block+1;
        R[i] = i*block;
    }
    R[num] = m;
    for(ll i = 1; i <= m; ++i)
        blog[i] = (i-1)/block+1;
    zt = z;
    for(int i = 1; i <= num; ++i)
        sort(zt.begin()+L[i],zt.begin()+R[i]+1);
}

inline int ask(int l, int r, int step)
{
    int x = lower_bound(zt.begin()+L[step],zt.begin()+R[step]+1,l)-zt.begin();
    int y = upper_bound(zt.begin()+L[step],zt.begin()+R[step]+1,r)-zt.begin()-1;
    return y-x+1;
}

inline void solve(int i)
{
    int tmp = q[i].s;
    for(int j = 1; j <= num; ++j)
        {
            int cnt = ask(q[i].l,q[i].r,j);
            if(tmp-cnt <= 0)
            {
                for(int k = L[j]; k <= R[j]; ++k)
                {
                    if(z[k] >= q[i].l && z[k] <= q[i].r)
                    {
                        tmp--;
                        if(tmp == 0)
                        {
                            ans[k]++;
                            return;
                        }
                    }
                }
            }
            tmp -= cnt;
        }
}
    
int main()
{
    freopen("shooting.in", "r", stdin);
    freopen("shooting.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> q[i].l >> q[i].r >> q[i].s;
    for(int i = 1; i <= m; ++i)
        cin >> z[i];
    build();
    
    for(int i = 1; i <= n; ++i)
        solve(i);
        
    for(int i = 1; i <= m; ++i)
        cout << ans[i] << '\n';
    
   	return 0;
}