Submission #1293124
Source Code Expand
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int N, M;
int L[300010], R[300010];
int l, r;
int l1[100010], r1[100010];
int sq;
double E = 1e-6;
int tree[300000];
int left2[300000], right2[300000];
int m;
int del[100010];
void addTree(int nd, int ll, int rr)
{
if(ll<=left2[nd] && rr>=right2[nd]){
tree[nd] ++;
return ;
}
if(ll>right2[nd] || rr<left2[nd])
return ;
addTree(2*nd, ll, rr);
addTree(2*nd+1, ll ,rr);
}
void solve()
{
int i, j;
m = 1;
while(m<M)
m *= 2;
for(i=0; i<m; i++){
left2[m+i] = i+1;
right2[m+i] = i+1;
}
for(i=m-1; i>=1; i--){
left2[i] = left2[2*i];
right2[i] = right2[2*i+1];
}
int n;
sq = (int)(sqrt(1.0*M)) + 1;
for(i=0; i<N; i++){
l = L[i], r = R[i];
n = 0;
for(j=1; j<=r && j<=sq; j++){
l1[n] = (l-1)/j+1;
r1[n] = r/j;
if(l1[n] <= r1[n] && r1[n]>sq){
if(l1[n] < sq+1)
l1[n] = sq+1;
n ++;
}
}
for(j=0; j<n/2; j++){
swap(l1[j], l1[n-1-j]);
swap(r1[j], r1[n-1-j]);
}
for(j=0; j<n; j++)
del[j] = 0;
int now = 0;
for(j=1; j<n; j++){
if(l1[j]<=r1[now]){
r1[now] = r1[j];
del[j] = 1;
}
else{
now = j;
}
}
for(j=0; j<n; j++){
if(del[j] == 0)
addTree(1, l1[j], r1[j]);
}
for(j=1; j<=sq&&j<=r; j++){
if(r/j - (l-1)/j > 0)
tree[m+j-1] ++;
}
}
for(i=1; i<=M; i++){
int sum = 0;
int nd = m+i-1;
while(nd>=1){
sum += tree[nd];
nd /= 2;
}
printf("%d\n", sum);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int i;
scanf("%d%d", &N, &M);
for(i=0; i<N; i++)
scanf("%d%d", &L[i], &R[i]);
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Snuke Line |
User |
treeofapple |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1721 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
7424 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:100:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.cpp:102:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &L[i], &R[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
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, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
4352 KB |
00_example_02.txt |
AC |
2 ms |
4352 KB |
01.txt |
AC |
2 ms |
4352 KB |
02.txt |
AC |
2 ms |
4352 KB |
03.txt |
AC |
2 ms |
4352 KB |
04.txt |
AC |
2 ms |
4352 KB |
05.txt |
AC |
2 ms |
4352 KB |
06.txt |
AC |
2 ms |
4352 KB |
07.txt |
AC |
2 ms |
4352 KB |
08.txt |
AC |
2 ms |
4352 KB |
09.txt |
AC |
2 ms |
4352 KB |
10.txt |
AC |
2 ms |
4352 KB |
11.txt |
AC |
795 ms |
6528 KB |
12.txt |
AC |
1128 ms |
7296 KB |
13.txt |
AC |
403 ms |
5376 KB |
14.txt |
AC |
297 ms |
5376 KB |
15.txt |
AC |
299 ms |
5376 KB |
16.txt |
AC |
698 ms |
5888 KB |
17.txt |
AC |
1119 ms |
7296 KB |
18.txt |
AC |
239 ms |
5248 KB |
19.txt |
AC |
1131 ms |
7296 KB |
20.txt |
AC |
1131 ms |
7296 KB |
21.txt |
AC |
1133 ms |
7296 KB |
22.txt |
AC |
1132 ms |
7296 KB |
23.txt |
AC |
1131 ms |
7296 KB |
24.txt |
AC |
1638 ms |
7040 KB |
25.txt |
AC |
734 ms |
5504 KB |
26.txt |
AC |
461 ms |
5376 KB |
27.txt |
TLE |
2103 ms |
6784 KB |
28.txt |
AC |
782 ms |
5504 KB |
29.txt |
AC |
1742 ms |
7168 KB |
30.txt |
AC |
686 ms |
5504 KB |
31.txt |
AC |
1455 ms |
7424 KB |
32.txt |
AC |
561 ms |
5632 KB |
33.txt |
AC |
346 ms |
5376 KB |
34.txt |
AC |
1550 ms |
7424 KB |
35.txt |
AC |
1546 ms |
7424 KB |
36.txt |
AC |
2 ms |
4352 KB |
37.txt |
AC |
11 ms |
6016 KB |