比赛 2024暑假C班集训B 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 天天爱射击 最终得分 100
用户昵称 darkMoon 运行时间 17.188 s
代码语言 C++ 内存使用 244.87 MiB
提交时间 2024-07-11 10:13:09
显示代码纯文本
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("shooting.in");
ofstream fout("shooting.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 2e5 + 5, Q = 505;
int n = mread(), m = mread(), l[N], r[N], a[N], x[N], ans[N], ma;
struct node{
    int l, r, s[N];
}s[Q];
signed main(){
    for(int i = 1; i <= n; i ++){
        l[i] = mread(), r[i] = mread(), a[i] = mread();
        ma = max(ma, r[i]);
    }
    for(int i = 1; i <= m; i ++){
        x[i] = mread();
    }
    int q = sqrt(m);
    for(int i = 1; i <= q; i ++){
        s[i].l = s[i - 1].r + 1;
        s[i].r = s[i].l + q - 1;
    }
    s[q].r = n;
    for(int i = 1; i <= q; i ++){
        for(int j = s[i].l; j <= s[i].r; j ++){
            s[i].s[x[j]] ++;
        }
        for(int j = 1; j <= ma; j ++){
            s[i].s[j] += s[i].s[j - 1];
        }
    }
    for(int i = 1; i <= n; i ++){
        int sum = 0;
        for(int j = 1; j <= q; j ++){
            int tmp = s[j].s[r[i]] - s[j].s[l[i] - 1];
            if(sum + tmp >= a[i]){
                for(int k = s[j].l; k <= s[j].r; k ++){
                    if(x[k] >= l[i] && x[k] <= r[i]){
                        sum ++;
                        if(sum == a[i]){
                            ans[k] ++;
                            break;
                        }
                    }
                }
                break;
            }
            else{
                sum += tmp;
            }
        }
    }
    for(int i = 1; i <= m; i ++){
        fout << ans[i] << "\n";
    }
    return 0;
}