oj.uz

Submission #57672

# Submission time Handle Problem Language Result Execution time Memory
57672 2018-07-15T19:06:58 Z Benq Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 1585 ms 263168 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500005;

ll N,Q, D[MX];

void input() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> Q;
    D[0] = 1;
    FOR(i,1,N+1) {
        cin >> D[i];
        D[i] = ((D[i]+D[i-1]-1)/D[i-1])*D[i-1];
        // cout << D[i] << "\n";
    }
}

ll getPos(ll T, ll M) {
    return (T/D[M])*D[M]-M;
}

ll get(int T, int hi) {
    int L = -1, R = N;
    while (L < R) {
        int M = (L+R+1)/2;
        if (getPos(T,M) >= hi) L = M;
        else R = M-1;
    }
    return L;
    // how many reporters >= position hi 
    // last reporter >= position hi 
}

int main() {
    input();
    F0R(i,Q) {
        int T,L,R; cin >> T >> L >> R;
        cout << get(T,L)-get(T,R+1) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 7272 KB Output is correct
2 Correct 1189 ms 7348 KB Output is correct
3 Correct 1076 ms 7400 KB Output is correct
4 Correct 1054 ms 7448 KB Output is correct
5 Correct 1117 ms 7500 KB Output is correct
6 Correct 990 ms 7664 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 7272 KB Output is correct
2 Correct 1189 ms 7348 KB Output is correct
3 Correct 1076 ms 7400 KB Output is correct
4 Correct 1054 ms 7448 KB Output is correct
5 Correct 1117 ms 7500 KB Output is correct
6 Correct 990 ms 7664 KB Output is correct
7 Correct 3 ms 7664 KB Output is correct
8 Correct 3 ms 7664 KB Output is correct
9 Correct 3 ms 7664 KB Output is correct
10 Correct 4 ms 7664 KB Output is correct
11 Correct 3 ms 7664 KB Output is correct
12 Correct 3 ms 7664 KB Output is correct
13 Correct 670 ms 21780 KB Output is correct
14 Correct 683 ms 38160 KB Output is correct
15 Correct 583 ms 53440 KB Output is correct
16 Correct 659 ms 69128 KB Output is correct
17 Correct 831 ms 89196 KB Output is correct
18 Correct 862 ms 107840 KB Output is correct
19 Correct 853 ms 126444 KB Output is correct
20 Correct 838 ms 145160 KB Output is correct
21 Correct 753 ms 163876 KB Output is correct
22 Correct 1051 ms 182500 KB Output is correct
23 Correct 1279 ms 201056 KB Output is correct
24 Correct 1388 ms 219760 KB Output is correct
25 Correct 1373 ms 235868 KB Output is correct
26 Correct 1585 ms 251280 KB Output is correct
27 Runtime error 1286 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
28 Halted 0 ms 0 KB -