Submission #128038

#	Time	Username	Problem	Language	Result	Execution time	Memory
128038		BThero	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1051 ms	39076 KiB

worst_reporter3

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)5e5 + 5;
const int K = 500;

ll trf[MAXN], lim[MAXN], need[MAXN];

ll arr[MAXN], B[MAXN / K + 5];

int id[MAXN];

int n, q;

void update(int p, ll x) {
    B[id[p]] -= arr[p];
    arr[p] = x;
    B[id[p]] += arr[p];
}

int query(ll x) {
    ll sum = 0;

    for (int i = 0; i <= id[n]; ++i) {
        if (sum + B[i] > x) {
            for (int j = max(1, i * K);; ++j) {
                sum += arr[j];

                if (sum > x) {
                    return j;
                }
            }            
        }

        sum += B[i];
    }

    return n + 1;
}

void solve() {
    scanf("%d %d", &n, &q);

    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &lim[i]);
    }

    trf[0] = 1;

    for (int i = 0; i < n; ++i) {
        trf[i + 1] = (lim[i + 1] + trf[i] - 1) / trf[i] * trf[i];
    }

    for (int i = 1; i <= n; ++i) {
        need[i] = trf[i] / trf[i - 1];
    }

    vector<int> nec;

    for (int i = 1; i <= n; ++i) {
        if (need[i] > 1) {
            nec.pb(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        arr[i] = 1;
        id[i] = i / K;
        B[id[i]] += arr[i];
    }

    for (int i = 1; i <= q; ++i) {
        ll l, r, t;
        int ans = 0;

        scanf("%lld %lld %lld", &t, &l, &r);

        if (l <= t && t <= r) {
            ++ans;
        }

        l = t - l;
        r = t - r;
        swap(l, r);

        for (int pos : nec) {
            ll cur = trf[pos - 1] * (t % need[pos]) + 1;
            update(pos, cur);
            t /= need[pos];
        }

        ans += query(r);
        ans -= query(l - 1);

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

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'void solve()':
worst_reporter3.cpp:64: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:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &lim[i]);
         ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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