oj.uz

Submission #838445

# Submission time Handle Problem Language Result Execution time Memory
838445 2023-08-27T00:09:15 Z NK_ Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 331 ms 15172 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

struct Scanner {
    FILE* stream;
    Scanner(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf;
    bool flush() { l = buf; r = l + fread(buf, 1, 1 << 20, stream); return l == r; }
    void get(char& c) { c = l == r && flush() ? ' ' : *l++; }
    friend Scanner& operator >>(Scanner& in, char& c) { return in.get(c), in; }
    friend Scanner& operator >>(Scanner& in, char* s) {
        for (in.get(s[0]); isspace(s[0]); in.get(s[0]));
        for (int i = 0; !isspace(s[i]) || (s[i] = '\0'); i++) in.get(s[i + 1]);
        return in;
    }
    friend Scanner& operator >>(Scanner& in, std::string& s) {
        char c;
        for (in.get(c); isspace(c); in.get(c));
        for (s = ""; !isspace(c); in.get(c)) s += c;
        return in;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        char c, f = '+';
        for (in.get(c); !isdigit(c); in.get(c))
            if constexpr (std::is_signed_v<T>) f = c;
        for (x = 0; isdigit(c); in.get(c)) x = x * (1 << 1) + x * (1 << 3) + c - '0';
        if constexpr (std::is_signed_v<T>) x = f == '-' ? -x : x;
        return in;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        std::string s; in >> s; x = std::stod(s);
        return in;
    }
    template <class T, class U>
    friend Scanner& operator >>(Scanner& in, std::pair<T, U>& a) {
        return in >> a.first >> a.second;
    }
    template <class T, size_t S>
    friend Scanner& operator >>(Scanner& in, std::array<T, S>& a) {
        for (int i = 0, n = S; i < n; i++) in >> a[i];
        return in;
    }
    template <class T>
    friend Scanner& operator >>(Scanner& in, std::vector<T>& a) {
        for (int i = 0, n = a.size(); i < n; i++) in >> a[i];
        return in;
    }
};
 
struct Printer {
    FILE* stream;
    Printer(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf + (1 << 20) - 1;
    int format = 0, precision = 15;
    ~Printer() { flush(); }
    void flush() { fwrite(buf, 1, l - buf, stream); l = buf; }
    void put(const char& c) { *l++ = c; if (l == r) flush(); }
    friend Printer& operator <<(Printer& out, const char& c) { return out.put(c), out; }
    friend Printer& operator <<(Printer& out, const char* s) {
        for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
        return out;
    }
    friend Printer& operator <<(Printer& out, const std::string& s) {
        for (int i = 0, n = s.size(); i < n; i++) out.put(s[i]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        static char s[40];
        static int i = 0;
        if (x == 0) { out.put('0'); return out; }
        if constexpr (std::is_signed_v<T>) x = x < 0 ? out.put('-'), -x : x;
        while (x > 0) s[++i] = x % 10 + '0', x /= 10;
        while (i > 0) out.put(s[i--]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        std::ostringstream oss;
        oss << std::fixed << std::setprecision(out.precision) << x;
        return out << oss.str();
    }
    template <class T, class U>
    friend Printer& operator <<(Printer& out, const std::pair<T, U>& a) {
        return out << a.first << " \n"[out.format > 1] << a.second;
    }
    template <class T, size_t S>
    friend Printer& operator <<(Printer& out, const std::array<T, S>& a) {
        out << a[0];
        for (int i = 1, n = S; i < n; i++) out << " \n"[out.format > 1] << a[i];
        return out;
    }
    template <class T>
    friend Printer& operator <<(Printer& out, const std::vector<T>& a) {
        if (!a.empty()) out << a[0];
        for (int i = 1, n = a.size(); i < n; i++) out << " \n"[out.format > 0] << a[i];
        return out;
    }
};

Scanner in(stdin);
Printer out(stdout);

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, Q; in >> N >> Q;
	vi D(N); for(auto& x : D) in >> x;

	ll mx = 1;
	vl MUL(N+1, 1), MOVE(N+1, 1);
	for(int i = 1; i <= N; i++) {
		MOVE[i] = MOVE[i - 1];
		if (mx < D[i - 1]) MOVE[i] = D[i - 1] + ((mx - (D[i - 1] % mx)) % mx);

		ll d = (MOVE[i] + mx - 1) / mx; 
		MUL[i] = min(MOD + 0LL, MUL[i - 1] * d);
		// cout << i << " => " << MUL[i] << " - " << MOVE[i] << " - " << d << endl;

		mx = max(mx, MOVE[i]);
	}

	auto get = [&](int t, int x) {
		int lo = 0, hi = N + 1;
		while(lo < hi) {
			int mid = (lo + hi) / 2;
			// cout << lo << " <= " << mid << " <= " << hi << endl;
			ll pos = (t / MUL[mid]) * MOVE[mid] - mid;
			// cout << t << " " << mid << " => " << pos << " - " << MUL[mid] << endl;

			if (pos <= x) hi = mid;
			else lo = mid + 1;
		}
		// cout << lo << " <<>> " << hi << endl;

		return N + 1 - lo;
	};

	for(int q = 0; q < Q; q++) {
		int t, l, r; in >> t >> l >> r;
		out << get(t, r) - get(t, l - 1) << nl;
	}

	exit(0-0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 15164 KB Output is correct
2 Correct 317 ms 15132 KB Output is correct
3 Correct 327 ms 15172 KB Output is correct
4 Correct 331 ms 15128 KB Output is correct
5 Correct 331 ms 15164 KB Output is correct
6 Correct 316 ms 15164 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 15164 KB Output is correct
2 Correct 317 ms 15132 KB Output is correct
3 Correct 327 ms 15172 KB Output is correct
4 Correct 331 ms 15128 KB Output is correct
5 Correct 331 ms 15164 KB Output is correct
6 Correct 316 ms 15164 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 122 ms 13104 KB Output is correct
14 Correct 120 ms 13064 KB Output is correct
15 Correct 119 ms 13000 KB Output is correct
16 Correct 123 ms 13072 KB Output is correct
17 Correct 183 ms 14540 KB Output is correct
18 Correct 182 ms 14492 KB Output is correct
19 Correct 184 ms 14540 KB Output is correct
20 Correct 184 ms 14488 KB Output is correct
21 Correct 188 ms 14540 KB Output is correct
22 Correct 182 ms 14492 KB Output is correct
23 Correct 186 ms 14596 KB Output is correct
24 Correct 187 ms 14520 KB Output is correct
25 Correct 319 ms 15168 KB Output is correct
26 Correct 321 ms 15152 KB Output is correct
27 Correct 230 ms 14984 KB Output is correct
28 Correct 210 ms 14836 KB Output is correct
29 Correct 219 ms 14820 KB Output is correct
30 Correct 226 ms 15036 KB Output is correct
31 Correct 224 ms 14876 KB Output is correct
32 Correct 211 ms 14644 KB Output is correct
33 Correct 1 ms 212 KB Output is correct