oj.uz

Submission #47602

# Submission time Handle Problem Language Result Execution time Memory
47602 2018-05-05T13:38:43 Z qoo2p5 Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 827 ms 5672 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 5e5 + 123;

int n, q;
int d[N];

void run() {
    cin >> n >> q;
    rep(i, 1, n + 1) {
        cin >> d[i];
    }
    rep(i, 2, n + 1) {
        d[i] = (d[i] + d[i - 1] - 1) / d[i - 1] * d[i - 1];
    }
    rep(i, 0, q) {
        int t, l, r;
        cin >> t >> l >> r;
        
        int L, R;
        
        {
            int left = 0;
            int right = n + 1;
            while (right - left > 1) {
                int mid = (left + right) / 2;
                int dist = l + mid;
                int k = (dist + d[mid] - 1) / d[mid];
                if (d[mid] * k <= t) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            L = left;
        }
        
        {
            int left = 0;
            int right = (n + 1);
            while (right - left > 1) {
                int mid = (left + right) / 2;
                int dist = r + mid + 1;
                int k = (dist + d[mid] - 1) / d[mid];
                if (d[mid] * k <= t) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            R = left;
        }
        
        cout << (L - R + (l <= t && t <= r)) << "\n";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 5296 KB Output is correct
2 Correct 791 ms 5416 KB Output is correct
3 Correct 770 ms 5476 KB Output is correct
4 Correct 801 ms 5672 KB Output is correct
5 Correct 760 ms 5672 KB Output is correct
6 Correct 827 ms 5672 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 5296 KB Output is correct
2 Correct 791 ms 5416 KB Output is correct
3 Correct 770 ms 5476 KB Output is correct
4 Correct 801 ms 5672 KB Output is correct
5 Correct 760 ms 5672 KB Output is correct
6 Correct 827 ms 5672 KB Output is correct
7 Correct 3 ms 5672 KB Output is correct
8 Correct 2 ms 5672 KB Output is correct
9 Correct 2 ms 5672 KB Output is correct
10 Correct 3 ms 5672 KB Output is correct
11 Correct 2 ms 5672 KB Output is correct
12 Correct 3 ms 5672 KB Output is correct
13 Runtime error 69 ms 5672 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -