Submission #2126361
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+20;
int n,m,c[N];
struct node{
int l,r,len;
}a[N];
bool cmp(node a,node b)
{
return a.len<b.len;
}
void update(int j,int k)
{
for(int i=j;i<=m;i+=(i&-i))
c[i]+=k;
}
int sum(int j)
{
int res=0;
for(int i=j;i>=1;i-=(i&-i))
res+=c[i];
return res;
}
int main()
{
while(cin>>n>>m)
{
memset(c,0,sizeof(c));//
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].len=a[i].r-a[i].l+1;
}
sort(a+1,a+n+1,cmp);
int k=1;
for(int d=1;d<=m;d++)
{
//O(m+nlogm)
for(;k<=n&&a[k].len<d;k++)//最多n次
{
update(a[k].l,1);
update(a[k].r+1,-1);//差分,[1..li..kd..ri,ri+1...m],树状数组统计前缀和
}
int ans=n-k+1;//区间长度>=d个数
//O(mlogm)
for(int e=d;e<=m;e+=d)
{
ans+=sum(e);
}
cout<<ans<<endl;
}
}
return 0;
}
Submission Info
Submission Time
2018-02-24 09:36:15+0900
Task
C - X: Yet Another Die Game
User
zjqaq
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1508 Byte
Status
WA
Exec Time
1 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i].l,&a[i].r);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 300
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt
All
00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
WA
1 ms
256 KB
00_example_02.txt
WA
1 ms
256 KB
01.txt
WA
1 ms
256 KB
02.txt
WA
1 ms
256 KB
03.txt
WA
1 ms
256 KB
04.txt
WA
1 ms
256 KB
05.txt
WA
1 ms
256 KB
06.txt
WA
1 ms
256 KB
07.txt
WA
1 ms
256 KB
08.txt
WA
1 ms
256 KB
09.txt
WA
1 ms
256 KB
10.txt
WA
1 ms
256 KB
11.txt
WA
1 ms
256 KB
12.txt
WA
1 ms
256 KB
13.txt
WA
1 ms
256 KB
14.txt
WA
1 ms
256 KB
15.txt
WA
1 ms
256 KB
16.txt
WA
1 ms
256 KB