Submission #128026

#	Time	Username	Problem	Language	Result	Execution time	Memory
128026		BThero	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	2076 ms	23492 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 ll INF = (ll)1e10;

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

ll t[MAXN << 2];

int n, q;

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = 1;
        return;
    }

    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);

    build(c1, tl, mid);
    build(c2, mid + 1, tr);

    t[v] = t[c1] + t[c2]; 
}

void update(int v, int tl, int tr, int p, ll x) {
    if (tl == tr) {
        t[v] = x;
        return;
    }

    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);

    if (p <= mid) {
        update(c1, tl, mid, p, x);
    }
    else {
        update(c2, mid + 1, tr, p, x);
    }

    t[v] = t[c1] + t[c2];
}

int query(int v, int tl, int tr, ll x) {
    if (v == 1 && t[v] <= x) {
        return n + 1;
    }

    if (tl == tr) {
        return tl;
    }

    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);

    if (t[c1] <= x) {
        return query(c2, mid + 1, tr, x - t[c1]);
    }    
    else {
        return query(c1, tl, mid, x);
    }
} 

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);
        }
    }

    build(1, 1, n);

    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(1, 1, n, pos, cur);
            t /= need[pos];
        }

        ans += query(1, 1, n, r);
        ans -= query(1, 1, n, 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:90: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:93: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:120: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: 0 / 81