比赛 EYOI暨SBOI暑假快乐赛3rd 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 Convoluted Intervals 最终得分 100
用户昵称 yrtiop 运行时间 1.447 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-27 10:08:15
显示代码纯文本
#include <bits/stdc++.h>
#define RE register
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int maxm = 1e4 + 5;
inline int read() {
    int s = 0;
    char c = getchar();
    for(;!isdigit(c);c = getchar());
    for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
    return s;
}
inline void write(ll x) {
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
    return ;
}
int a[maxn],b[maxn],n,m;
int sum1[maxm],sum2[maxm],tot,cnt1[maxm],cnt2[maxm];
int main() {
    freopen("Convoluted_Intervals.in","r",stdin);
    freopen("Convoluted_Intervals.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(RE int i = 1;i <= n;++ i)a[i] = read(),b[i] = read(),++ sum1[a[i]],++ sum2[b[i]];
    tot = m << 1;
    cnt1[0] = sum1[0];
    cnt2[0] = sum2[0];
    for(RE int i = 1;i <= tot;++ i)cnt1[i] = sum1[i],cnt2[i] = sum2[i],sum1[i] += sum1[i - 1],sum2[i] += sum2[i - 1];
    for(RE int k = 0;k <= tot;++ k) {
        ll ans = 0;
        int t1 = sum2[tot] - sum2[k - 1],t2 = sum1[tot] - sum1[k];
        ans += 1ll * t1 * sum2[tot] - 1ll * t2 * sum1[tot];
        for(RE int i = 0;i < k;++ i) {
            if(i > m)break ;
            ans += 1ll * cnt2[i] * (sum2[tot] - sum2[k - i - 1]) - 1ll *  cnt1[i] * (sum1[tot] - sum1[k - i]);
        }
        ans -= 1ll * cnt1[k] * (sum1[tot] - sum1[0]);
        write(ans);
        puts("");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}