Submission #1383180
Source Code Expand
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
typedef long long ll;
template<typename T>
struct BIT {
vector<T> data;
BIT() {}
BIT(int n) : data(n+1, 0) {}
void init(int n) { data.assign(n+1, 0); }
T sum(int ed) const {
for(T res(0); ; ed &= ed-1) if(ed) res += data[ed]; else return res;
}
void add(int i, const T& x) {
for(++i; i < (int)data.size(); i += i&-i) data[i] += x;
}
};
BIT<int> bit(100000+5);
void go(int a, int b) {
bit.add(0, 1);
bit.add(b-a+1, -1);
int c1 = b-a+1;
int c2 = b+1;
for(int i = 1; ; ++i) {
int aa = (a+i-1)/i;
int bb = b/i;
if(aa > bb)
continue;
int lb = max(aa, c1+1);
int ub = min(bb, c2-1);
if(lb > ub)
break;
bit.add(lb-1, 1);
bit.add(ub, -1);
c2 = lb;
}
}
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
REP(i, n) {
int a, b;
scanf("%d%d", &a, &b);
go(a, b);
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", bit.sum(i));
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Snuke Line |
User |
ush |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1253 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
1280 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:50:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:53:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
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 |
1 ms |
640 KB |
00_example_02.txt |
AC |
1 ms |
640 KB |
01.txt |
AC |
1 ms |
640 KB |
02.txt |
AC |
2 ms |
640 KB |
03.txt |
AC |
1 ms |
640 KB |
04.txt |
AC |
1 ms |
640 KB |
05.txt |
AC |
1 ms |
640 KB |
06.txt |
AC |
1 ms |
640 KB |
07.txt |
AC |
1 ms |
640 KB |
08.txt |
AC |
1 ms |
640 KB |
09.txt |
AC |
2 ms |
640 KB |
10.txt |
AC |
1 ms |
640 KB |
11.txt |
AC |
1316 ms |
896 KB |
12.txt |
AC |
98 ms |
1280 KB |
13.txt |
AC |
154 ms |
640 KB |
14.txt |
AC |
287 ms |
640 KB |
15.txt |
AC |
288 ms |
640 KB |
16.txt |
AC |
1381 ms |
768 KB |
17.txt |
AC |
110 ms |
1152 KB |
18.txt |
AC |
209 ms |
640 KB |
19.txt |
AC |
99 ms |
1280 KB |
20.txt |
AC |
98 ms |
1280 KB |
21.txt |
AC |
99 ms |
1280 KB |
22.txt |
AC |
98 ms |
1280 KB |
23.txt |
AC |
98 ms |
1280 KB |
24.txt |
TLE |
2103 ms |
640 KB |
25.txt |
TLE |
2103 ms |
640 KB |
26.txt |
AC |
1434 ms |
640 KB |
27.txt |
AC |
991 ms |
1024 KB |
28.txt |
TLE |
2103 ms |
640 KB |
29.txt |
AC |
531 ms |
1024 KB |
30.txt |
TLE |
2103 ms |
640 KB |
31.txt |
AC |
73 ms |
1280 KB |
32.txt |
AC |
72 ms |
768 KB |
33.txt |
AC |
70 ms |
640 KB |
34.txt |
AC |
1597 ms |
1280 KB |
35.txt |
AC |
1597 ms |
1280 KB |
36.txt |
AC |
1 ms |
640 KB |
37.txt |
AC |
10 ms |
768 KB |