Submission #171868

#	Time	Username	Problem	Language	Result	Execution time	Memory
171868		arnold518	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	606 ms	39008 KiB

worst_reporter3

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

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

const int MAXN = 5e5;

struct Query
{
    ll t, l, r;
};

int N, Q;
ll D[MAXN+10];
Query A[MAXN+10];
int ans[MAXN+10];

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);

    D[0]=1;
    for(i=1; i<=N; i++) scanf("%lld", &D[i]);
    for(i=1; i<=N; i++) D[i]=(D[i]+D[i-1]-1)/D[i-1]*D[i-1];
    for(i=1; i<=Q; i++) scanf("%lld%lld%lld", &A[i].t, &A[i].l, &A[i].r);

    vector<ll> V;
    for(i=0; i<=N; i++) V.push_back(D[i]);
    V.erase(unique(V.begin(), V.end()), V.end());

    for(auto it : V)
    {
        ll s, e;
        e=lower_bound(D, D+N+1, it)-D;
        s=upper_bound(D, D+N+1, it)-D-1;
        s*=-1; e*=-1;

        for(i=1; i<=Q; i++)
        {
            ll ss=s+A[i].t/it*it;
            ll ee=e+A[i].t/it*it;

            ans[i]+=max(0ll, min(ee, A[i].r)-max(ss, A[i].l)+1);
        }
    }

    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:22:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
worst_reporter3.cpp:24: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:27:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &D[i]);
                         ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:29:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=Q; i++) scanf("%lld%lld%lld", &A[i].t, &A[i].l, &A[i].r);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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