Submission #3006776

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

void solve(int N,int M,vi& l,vi& r) {
    int sq = sqrt(M); // 316
    bool just = (sq*sq == M);

    vi a(M+2, 0);

    vi left;
    left.reserve(sq+1);

    rep(i,N){ // 3e5
        double li=l[i], ri=r[i];
#ifdef DEBUG
        fprintf(stderr, "i=%d (%g..%g)\n", i, li, ri);
#endif
        a[l[i]]++; a[r[i]+1]--;
#ifdef DEBUG
        fprintf(stderr, "  [%g %g]\n", li, ri);
#endif
        int last_lo = li;
        left.clear();
        left.pb(1);
        for (int x=2; x<=sq; ++x) { // 316 ; < 9.5e7
            int lo=ceil(li/x), hi=floor(ri/x);
            hi = min(last_lo-1, hi);
            if (lo <= hi) {
#ifdef DEBUG
                fprintf(stderr, "  [%d %d]*%d\n", lo, hi, x);
#endif
                a[lo]++; a[hi+1]--;
                left.pb(x);
                last_lo = lo;
            }
        }
        if (just && sq < last_lo) {
            a[sq]++; a[sq+1]--;
            last_lo = sq;
#ifdef DEBUG
            fprintf(stderr, "  [%d] // sq\n", sq);
#endif
        }
#ifdef DEBUG
        cerr << "left=" << left << last_lo << endl;
#endif
#if 1
        for (int x : left) {
            if (x >= last_lo) break;
#ifdef DEBUG
            fprintf(stderr, "  [%d]\n", x);
#endif
            a[x]++; a[x+1]--;
        }
#endif
        // rep(i,M+1) a[i+1] += a[i];
        // cerr << i << ") " << a << endl;
        // a.assign(M+2, 0);
    }

    rep(i,M+1) a[i+1] += a[i];

    for (int i=1; i<=M; ++i) {
        cout << a[i] << 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 3002 Byte
Status
Exec Time 1197 ms
Memory 3712 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110: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:114: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 695 ms 2944 KB
12.txt 1099 ms 3584 KB
13.txt 307 ms 2688 KB
14.txt 207 ms 2560 KB
15.txt 206 ms 2560 KB
16.txt 588 ms 2944 KB
17.txt 1088 ms 3584 KB
18.txt 142 ms 2560 KB
19.txt 1107 ms 3584 KB
20.txt 1103 ms 3584 KB
21.txt 1119 ms 3584 KB
22.txt 1111 ms 3584 KB
23.txt 1111 ms 3584 KB
24.txt 1175 ms 3328 KB
25.txt 397 ms 2688 KB
26.txt 238 ms 2560 KB
27.txt 1188 ms 3456 KB
28.txt 400 ms 2688 KB
29.txt 1197 ms 3328 KB
30.txt 388 ms 2688 KB
31.txt 1067 ms 3712 KB
32.txt 362 ms 2688 KB
33.txt 217 ms 2688 KB
34.txt 1121 ms 3712 KB
35.txt 1118 ms 3712 KB
36.txt 1 ms 256 KB
37.txt 152 ms 768 KB