oj.uz

Submission #128026

# Submission time Handle Problem Language Result Execution time Memory
128026 2019-07-10T10:37:21 Z BThero Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 23492 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 682 ms 23416 KB Output is correct
2 Correct 612 ms 23492 KB Output is correct
3 Correct 615 ms 23316 KB Output is correct
4 Correct 682 ms 23288 KB Output is correct
5 Correct 660 ms 23416 KB Output is correct
6 Correct 698 ms 23476 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 23416 KB Output is correct
2 Correct 612 ms 23492 KB Output is correct
3 Correct 615 ms 23316 KB Output is correct
4 Correct 682 ms 23288 KB Output is correct
5 Correct 660 ms 23416 KB Output is correct
6 Correct 698 ms 23476 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 674 ms 21216 KB Output is correct
14 Correct 666 ms 21332 KB Output is correct
15 Correct 566 ms 21368 KB Output is correct
16 Correct 662 ms 21360 KB Output is correct
17 Execution timed out 2076 ms 22912 KB Time limit exceeded
18 Halted 0 ms 0 KB -