Submission #3008242

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

// Fenwick Tree (Binary Indexed Tree, BIT)

template <typename T, int base=0>
class fenwick_tree_0 { // 0-base
 public:
    vector<T> x;
 public:
    fenwick_tree_0(int n) : x(n+base,0) { }
    void add(int k, T a) { for (; k<x.size(); k|=k+1) x[k] += a; }
    T sum(int i, int j) { // [i,j]
        if (i == base) {
            T S = 0; for (; j>=0; j=(j&(j+1))-1) S += x[j]; return S;
        } else {
            return sum(base, j) - sum(base, i-1);
        }
    }
};

template <typename T, int base=1>
class fenwick_tree_1 { // 1-base
 public:
    vector<T> x;
 public:
    fenwick_tree_1(int n) : x(n+base,0) { }
    void add(int k, T a) { for (; k<=x.size(); k+=k&-k) x[k] += a; }
    T sum(int i, int j) { // [i,j]
        if (i == base) {
            T S = 0; for (; j>0; j-=j&-j) S += x[j]; return S;
        } else {
            return sum(base, j) - sum(base, i-1);
        }
    }
};

template <typename F, typename T, int base>
class double_fenwick_tree {
public:
    F p, q;
public:
    double_fenwick_tree(int n) : p(n), q(n) { }

    void add_range(int a, int b, T w) {
        p.add(a, -w*a); p.add(b, w*b);
        q.add(a, w); q.add(b, -w);
    }
#if 0
    T sum(int i, int j) { // [i, j]
        if (i == base) {
            return p.sum(base, j) + j*q.sum(base, j);
        } else {
            return sum(base, j+1) - sum(base, i);
        }
    }
#else
    T sum(int i, int j) { // [i, j)
        if (i == base) {
            return p.sum(base, j) + j*q.sum(base, j);
        } else {
            return sum(base, j) - sum(base, i);
        }
    }
#endif
};

void solve(int N,int M,vi& l,vi& r) {
    double_fenwick_tree<fenwick_tree_0<int>, int, 0> bw(M+2);
    vvi lr(M+1);
    rep(i,N){
        int w = r[i] - l[i] + 1;
        lr[w].pb(i);
        bw.add_range(1, w+1, 1);
    }

    double_fenwick_tree<fenwick_tree_0<int>, int, 0> fw(M+2);
    rep1(d,M){
        int ans = bw.sum(d,d+1);

        for (int i: lr[d-1]) {
            // 区間[ l_i, r_i ]++
            fw.add_range(l[i], r[i]+1, 1);
        }
        for (int x=d; x<=M; x+=d) {
            ans += fw.sum(x,x+1);
        }

        cout << ans << endl;
    }
}

int main() {
    char buf[128];
    int N, M;
    // cin >> N >> M;
    scanf("%d %d", &N, &M);
    vi l(N),r(N);
    rep(i, N) {
        // cin >> l[i] >> r[i];
        scanf("%d %d", &l[i], &r[i]);
    }
    solve(N,M,l,r);
    return 0;
}

Submission Info

Submission Time
Task E - Snuke Line
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3721 Byte
Status
Exec Time 370 ms
Memory 10240 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:135:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
./Main.cpp:139:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l[i], &r[i]);
                                     ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
All 700 / 700 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 1 ms 256 KB
00_example_02.txt 1 ms 256 KB
01.txt 1 ms 256 KB
02.txt 2 ms 256 KB
03.txt 2 ms 256 KB
04.txt 1 ms 256 KB
05.txt 3 ms 256 KB
06.txt 3 ms 256 KB
07.txt 1 ms 256 KB
08.txt 2 ms 256 KB
09.txt 1 ms 256 KB
10.txt 1 ms 256 KB
11.txt 203 ms 6784 KB
12.txt 365 ms 10240 KB
13.txt 98 ms 4864 KB
14.txt 81 ms 4480 KB
15.txt 81 ms 4480 KB
16.txt 157 ms 6144 KB
17.txt 356 ms 10112 KB
18.txt 74 ms 4480 KB
19.txt 366 ms 10240 KB
20.txt 366 ms 10240 KB
21.txt 370 ms 10240 KB
22.txt 362 ms 10240 KB
23.txt 362 ms 10240 KB
24.txt 338 ms 8320 KB
25.txt 100 ms 4732 KB
26.txt 78 ms 4348 KB
27.txt 348 ms 8704 KB
28.txt 104 ms 4988 KB
29.txt 345 ms 8960 KB
30.txt 106 ms 4984 KB
31.txt 312 ms 8960 KB
32.txt 96 ms 4864 KB
33.txt 76 ms 4480 KB
34.txt 332 ms 8832 KB
35.txt 327 ms 8832 KB
36.txt 1 ms 256 KB
37.txt 216 ms 4352 KB