Submission #180308

#	Time	Username	Problem	Language	Result	Execution time	Memory
180308		Akashi	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	709 ms	25504 KiB

worst_reporter3

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

const int INF = 1e9 + 1e6;

int n, q;
int d[500005], ad[500005];

inline int get_pos(int t, int i){
    int wh = t / d[i];
    return wh * d[i] - ad[i];
}

inline int count_kids(int t, int x){
    int st = 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(get_pos(t, mij) <= x) st = mij + 1;
        else dr = mij - 1;
    }

    return dr;
}

int main()
{
    scanf("%d%d", &n, &q);

    d[1] = 1; ++n;
    ad[1] = 0;
    for(int i = 2; i <= n ; ++i){
        scanf("%d", &d[i]);
        ad[i] = i - 1;
        int k = d[i] / d[i - 1];
        if(d[i] % d[i - 1]) ++k;
        if(1LL * d[i - 1] * k >= INF) d[i] = INF;
        else d[i] = d[i - 1] * k;
    }

    for(int i = 1; i <= n / 2 ; ++i) swap(d[i], d[n - i + 1]), swap(ad[i], ad[n - i + 1]);

    int t, l, r;
    while(q--){
        scanf("%d%d%d", &t, &l, &r);
        if(l > t) {printf("0\n"); continue ;}

        r = min(r, t);
        int nr = count_kids(t, r) - count_kids(t, l - 1);
        printf("%d\n", nr);
    }

    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
worst_reporter3.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81