oj.uz

Submission #128038

# Submission time Handle Problem Language Result Execution time Memory
128038 2019-07-10T10:49:12 Z BThero Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1051 ms 39076 KB 
// 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 21240 KB Output is correct
2 Correct 1018 ms 21124 KB Output is correct
3 Correct 1048 ms 21148 KB Output is correct
4 Correct 1020 ms 21048 KB Output is correct
5 Correct 1020 ms 20984 KB Output is correct
6 Correct 1022 ms 21128 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 21240 KB Output is correct
2 Correct 1018 ms 21124 KB Output is correct
3 Correct 1048 ms 21148 KB Output is correct
4 Correct 1020 ms 21048 KB Output is correct
5 Correct 1020 ms 20984 KB Output is correct
6 Correct 1022 ms 21128 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 556 ms 18972 KB Output is correct
14 Correct 429 ms 18936 KB Output is correct
15 Correct 405 ms 19040 KB Output is correct
16 Correct 424 ms 18936 KB Output is correct
17 Correct 819 ms 20412 KB Output is correct
18 Correct 863 ms 39076 KB Output is correct
19 Correct 825 ms 39032 KB Output is correct
20 Correct 827 ms 39036 KB Output is correct
21 Correct 830 ms 38984 KB Output is correct
22 Correct 817 ms 39048 KB Output is correct
23 Correct 835 ms 38856 KB Output is correct
24 Correct 808 ms 39044 KB Output is correct
25 Correct 1047 ms 36524 KB Output is correct
26 Correct 1030 ms 36600 KB Output is correct
27 Correct 1008 ms 38776 KB Output is correct
28 Correct 1000 ms 38980 KB Output is correct
29 Correct 1039 ms 38680 KB Output is correct
30 Correct 1051 ms 38476 KB Output is correct
31 Correct 987 ms 38888 KB Output is correct
32 Correct 794 ms 35192 KB Output is correct
33 Correct 2 ms 376 KB Output is correct