Submission #5408006


Source Code Expand

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

static void print_int(i64 n){if(n<0){putchar('-');n=-n;}if(n==0){putchar('0');return;}int s[20],len=0;while(n>0){s[len++]=n%10+'0';n/=10;}while(len>0){putchar(s[--len]);}}
static i64 read_int(void){int prev='\0';int c=getchar();while(!('0'<=c && c<='9')){prev=c;c=getchar();}i64 res=0;while('0'<=c && c<='9'){res=10*res+c-'0';c=getchar();}return prev=='-'?-res:res;}

typedef struct range {
  i32 l, r;
} range;

void add (i32 *bit, i32 x, i32 v) {
  i32 n = bit[0];
  for (i32 i = x; i <= n; i += i & -i) {
    bit[i] += v;
  }
}

i32 find (i32 *bit, i32 x) {
  i32 sum = 0;
  for (i32 i = x; i > 0; i -= i & -i) {
    sum += bit[i];
  }
  return sum;
}

void run (void) {
  i32 n = read_int();
  i32 m = read_int();
  range **p = (range **) calloc (m + 1, sizeof (range *));
  i32 *len = (i32 *) calloc (2 * (m + 1), sizeof (i32));
  i32 *max_len = len + m + 1;
  for (i32 i = 0; i < n; ++i) {
    i32 l = read_int();
    i32 r = read_int() + 1;
    i32 d = r - l;
    if (len[d] == max_len[d]) {
      max_len[d] = 2 * max_len[d] + 1;
      p[d] = realloc (p[d], max_len[d]);
    }
    p[d][len[d]++] = (range) {l, r};
  }
  i32 *bit = (i32 *) calloc (m + 2, sizeof (i32));
  bit[0] = m + 1;
  for (i32 d = 1, c = 0; d <= m; ++d) {
    for (i32 i = 0; i < len[d - 1]; ++i) {
      c++;
      add (bit, p[d - 1][i].l, 1);
      add (bit, p[d - 1][i].r, -1);
    }
    i32 ans = n - c;
    for (i32 j = d; j <= m; j += d) {
      ans += find (bit, j);
    }
    print_int (ans);
    putchar ('\n');
  }
}

int main (void) {
  run();
  return 0;
}

Submission Info

Submission Time
Task E - Snuke Line
User sansen
Language C (GCC 5.4.1)
Score 0
Code Size 1756 Byte
Status RE
Exec Time 100 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 8
WA × 1
RE × 30
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 128 KB
00_example_02.txt AC 1 ms 128 KB
01.txt WA 1 ms 128 KB
02.txt RE 95 ms 128 KB
03.txt RE 96 ms 128 KB
04.txt RE 95 ms 128 KB
05.txt AC 1 ms 128 KB
06.txt AC 1 ms 128 KB
07.txt RE 95 ms 128 KB
08.txt AC 1 ms 128 KB
09.txt RE 95 ms 128 KB
10.txt AC 1 ms 128 KB
11.txt RE 96 ms 768 KB
12.txt RE 96 ms 1664 KB
13.txt RE 95 ms 256 KB
14.txt RE 96 ms 256 KB
15.txt RE 95 ms 256 KB
16.txt RE 96 ms 640 KB
17.txt RE 98 ms 1664 KB
18.txt RE 96 ms 128 KB
19.txt RE 98 ms 1792 KB
20.txt RE 96 ms 1664 KB
21.txt RE 97 ms 1664 KB
22.txt RE 97 ms 1792 KB
23.txt RE 96 ms 1664 KB
24.txt RE 97 ms 896 KB
25.txt RE 96 ms 384 KB
26.txt RE 96 ms 256 KB
27.txt RE 96 ms 1024 KB
28.txt RE 96 ms 384 KB
29.txt RE 97 ms 1024 KB
30.txt RE 100 ms 384 KB
31.txt RE 96 ms 896 KB
32.txt RE 95 ms 384 KB
33.txt RE 95 ms 256 KB
34.txt RE 96 ms 896 KB
35.txt RE 96 ms 896 KB
36.txt AC 1 ms 128 KB
37.txt AC 16 ms 1152 KB