oj.uz

Submission #203266

# Submission time Handle Problem Language Result Execution time Memory
203266 2020-02-20T02:21:04 Z tri Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 11560 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int MAXN = 5e5 + 10;
ll d[MAXN], c[MAXN];

int N, Q;

ll fPos(int i, ll t) {
    ll step = t / c[i];
    return -i + step * c[i];
}

// returns number of people with position >= lBound
ll searchAfter(ll lBound, ll t) {
    int low = 0;
    int hi = N + 1;

    while (low != hi) {
        int mid = (low + hi + 1) / 2;

        if (fPos(mid - 1, t) >= lBound) {
            low = mid;
        } else {
            hi = mid - 1;
        }
    }
    return low;
}


int main() {
    cin >> N >> Q;

    for (int i = 1; i <= N; i++) {
        cin >> d[i];
    }
    c[0] = 1;

    for (int i = 1; i <= N; i++) {
        ll step = (d[i] + c[i - 1] - 1) / c[i - 1];
        c[i] = step * c[i - 1];
    }

    for (int q = 0; q < Q; q++) {
        ll t, l, r;
        cin >> t >> l >> r;

        ll lCnt = searchAfter(l, t);
        ll rCnt = searchAfter(r + 1, t);

        ll cnt = lCnt - rCnt;
        cout << cnt << endl;
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 11560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 11560 KB Time limit exceeded
2 Halted 0 ms 0 KB -