比赛 |
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;
}