Submission #1515565
Source Code Expand
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
public Solve(){}
StringBuilder sb;
public static int Main(){
new Solve().Run();
return 0;
}
void Run(){
sb = new StringBuilder();
Calc();
Console.Write(sb.ToString());
}
void Calc(){
string[] str = Console.ReadLine().Split(' ');
int N = int.Parse(str[0]);
int M = int.Parse(str[1]);
Data[] D = new Data[N];
for(int i=0;i<N;i++){
str = Console.ReadLine().Split(' ');
D[i] = new Data(int.Parse(str[0]),int.Parse(str[1]));
}
Array.Sort(D,(x,y)=>(x.space - y.space));
SegTree Seg = new SegTree(M+1,this);
int p = 0;
for(int i=1;i<=M;i++){
int count;
while(p < N && D[p].space < i){
Seg.Add(D[p].l,D[p].r);
p++;
}
count = N-p;
for(int j=i;j<=M;j+=i){
count += Seg.Get(j);
}
sb.Append(count+"\n");
}
}
}
struct SegTree{
Solve Sol;
public int[] X;
//葉の最初の場所
public int segf;
//segfのbit
public int segfb;
//葉の深さの内浅い方
public int depth;
//浅い葉の内座標が最大のもの
public int borderP;
//はみ出すものの数
public int border;
public SegTree(int N,Solve So){
Sol = So;
X = new int[2*N-1];
for(depth = 1;(1 << depth) <= N;depth++){
;
}
segf = N-1;
borderP = (1 << depth) - 2;
border = 2*N - borderP - 2;
segfb = border/2;
}
public int ToBit(int p){
if(p >= border){
return segfb + p - border;
}
else{
return p;
}
}
//葉のある場所
public int ToLeaf(int p){
if(p >= border){
return segf + p - border;
}
else{
return borderP + p + 1;
}
}
//葉の示す頂点
public int ToPoint(int leaf){
if(leaf > borderP){
return leaf - borderP - 1;
}
else{
return leaf - segf + border;
}
}
public int Get(int p){
int C = 0;
//葉の作業
C += X[ToLeaf(p)];
//親の作業
for(int v=ToLeaf(p);v!=0;v=(v-1)/2){
int spa = (v-1)/2;
C += X[spa];
}
return C;
}
void Act(int v){
X[v]++;
}
//vの子の内bより大きいものに(bは子孫,bはToBitしたもの)
void More(int b,int v,int depth){
if((b & (1 << depth)) == 0){
//右の子は全てbより大きい
if(((b+1) % (1 << depth)) != 0){
More(b,v*2+1,depth-1);
Act(v*2+2);
}
else{
Act(v*2+2);
}
}
else{
//左の子は全てb未満
More(b,v*2+2,depth-1);
}
}
//vの子の内bより小さなものに(bは子孫,bはToBitしたもの)
void Less(int b,int v,int depth){
if((b & (1 << depth)) == 0){
//右の子は全てbより大きい
Less(b,v*2+1,depth-1);
}
else{
//左の子は全てb未満
if(b % (1 << depth) != 0){
Act(v*2+1);
Less(b,v*2+2,depth-1);
}
else{
//右の子は全てb以上
Act(v*2+1);
}
}
}
void Section(int bl,int br,int v,int dl,int dr){
if(v >= segf){
//葉
Act(v);
}
else{
if((bl & (1 << dl)) == 0 && (br & (1 << dr)) == 0){
//両方左
Section(bl,br,v*2+1,dl-1,dr-1);
}
else if((bl & (1 << dl)) != 0 && (br & (1 << dr)) != 0){
//両方右
Section(bl,br,v*2+2,dl-1,dr-1);
}
else{
//左と右に分かれた
if(bl % (1 << dl) != 0){
More(bl-1,v*2+1,dl-1);
}
else{
//左は全て含まれる
Act(v*2+1);
}
if((br + 1) % (1 << dl) != 0){
Less(br+1,v*2+2,dr-1);
}
else{
//右は全て含まれる
Act(v*2+2);
}
}
}
}
public void Add(int l0,int r0){
int bl = ToBit(l0);
int br = ToBit(r0);
int dl = l0 >= border ? depth - 2 : depth - 1;
int dr = r0 >= border ? depth - 2 : depth - 1;
Section(bl,br,0,dl,dr);
}
}
struct Data{
public int l;
public int r;
public int space;
public Data(int l0,int r0){
l = l0;
r = r0;
space = r0-l0+1;
}
}
Submission Info
Submission Time |
|
Task |
E - Snuke Line |
User |
leign |
Language |
C# (Mono 4.6.2.0) |
Score |
700 |
Code Size |
5201 Byte |
Status |
AC |
Exec Time |
553 ms |
Memory |
24976 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 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 |
25 ms |
11348 KB |
00_example_02.txt |
AC |
22 ms |
11220 KB |
01.txt |
AC |
22 ms |
11220 KB |
02.txt |
AC |
24 ms |
11308 KB |
03.txt |
AC |
22 ms |
9172 KB |
04.txt |
AC |
22 ms |
9300 KB |
05.txt |
AC |
22 ms |
13268 KB |
06.txt |
AC |
23 ms |
11220 KB |
07.txt |
AC |
22 ms |
9172 KB |
08.txt |
AC |
23 ms |
13268 KB |
09.txt |
AC |
23 ms |
13376 KB |
10.txt |
AC |
21 ms |
11220 KB |
11.txt |
AC |
455 ms |
20244 KB |
12.txt |
AC |
537 ms |
22416 KB |
13.txt |
AC |
402 ms |
18972 KB |
14.txt |
AC |
392 ms |
18716 KB |
15.txt |
AC |
383 ms |
16668 KB |
16.txt |
AC |
440 ms |
17688 KB |
17.txt |
AC |
541 ms |
22288 KB |
18.txt |
AC |
387 ms |
16668 KB |
19.txt |
AC |
541 ms |
22416 KB |
20.txt |
AC |
536 ms |
22416 KB |
21.txt |
AC |
553 ms |
20368 KB |
22.txt |
AC |
543 ms |
22416 KB |
23.txt |
AC |
541 ms |
20368 KB |
24.txt |
AC |
487 ms |
18960 KB |
25.txt |
AC |
392 ms |
16920 KB |
26.txt |
AC |
376 ms |
18716 KB |
27.txt |
AC |
508 ms |
21520 KB |
28.txt |
AC |
409 ms |
18968 KB |
29.txt |
AC |
527 ms |
19344 KB |
30.txt |
AC |
420 ms |
17044 KB |
31.txt |
AC |
525 ms |
22928 KB |
32.txt |
AC |
427 ms |
19096 KB |
33.txt |
AC |
397 ms |
16792 KB |
34.txt |
AC |
515 ms |
22928 KB |
35.txt |
AC |
511 ms |
24976 KB |
36.txt |
AC |
21 ms |
9172 KB |
37.txt |
AC |
120 ms |
16988 KB |