Submission #45473

#	Time	Username	Problem	Language	Result	Execution time	Memory
45473		choikiwon	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	825 ms	262144 KiB

worst_reporter3

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

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 500010;

int N, Q;
int D[MN];
vector<pair<pii, int> > seg;

int main() {
    scanf("%d %d", &N, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &D[i]);
    }

    int d = D[0];
    int s = 0;
    int c = 1;
    int pos = 0;
    while(1) {
        while(pos < N && D[pos] <= d) pos++;
        seg.push_back({ {s, pos - 1}, c });
        if(pos == N) break;
        s = pos;
        int k = 1;
        while(D[pos] > k * d) k++;
        d = k * d;
        c = k * c;
    }

    for(int i = 0; i < Q; i++) {
        int t, l, r; scanf("%d %d %d", &t, &l, &r);

        int ans = l <= t && t <= r;
        t /= D[0];

        for(int j = 0; j < seg.size(); j++) {
            pii s = seg[j].first;
            int m = seg[j].second;

            int x = (t / m) * m;

            //cout << m << ' ' << x << ' ' << s.first << ' ' << s.second << endl;

            if(x * D[0] - s.first - 1 < l || r < x * D[0] - s.second - 1) continue;
            int tl = max(x * D[0] - s.second - 1, l);
            int tr = min(x * D[0] - s.first - 1, r);
            ans += tr - tl + 1;
        }

        printf("%d\n", ans);
    }
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:41:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < seg.size(); j++) {
                        ~~^~~~~~~~~~~~
worst_reporter3.cpp:14: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:17: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:36:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, l, r; scanf("%d %d %d", &t, &l, &r);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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