oj.uz

Submission #210825

# Submission time Handle Problem Language Result Execution time Memory
210825 2020-03-18T18:30:13 Z bash Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1162 ms 29392 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}
#define int ll

int A[MAXN];
int D[MAXN];
int n, q;

int val(int T, int pos) {
	int per = T / A[pos];
	return per * A[pos] - pos;	
}

int solve(int T, int x) {
	/// A[i - 1] > A[i]
	/// find max i that a[i] <= x
	int l = 1, r = n;
	int ans = n + 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if (val(T, mid) <= x) {
			ans = mid;
			r = mid - 1;			
		} else {
			l = mid + 1;
		}
	}
	return n - ans + 1;	
}

main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    n = readInt(), q = readInt();
    for (int i = 1; i <= n; i++) {
    	D[i] = readInt();
    }
    A[1] = D[1];
    for (int i = 2; i <= n; i++) {
    	A[i] = A[i - 1] * ((D[i] + A[i - 1] - 1)  / A[i - 1]);
    }
	while(q--) {
		int T = readInt(), L = readInt(), R = readInt();
		cout << solve(T, R) - solve(T, L - 1) + (L <= T && T <= R) << endl;
	}
	return 0;
}

Compilation message

worst_reporter3.cpp:106:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 11940 KB Output is correct
2 Correct 966 ms 12272 KB Output is correct
3 Correct 1068 ms 12320 KB Output is correct
4 Correct 1162 ms 12284 KB Output is correct
5 Correct 1029 ms 12240 KB Output is correct
6 Correct 857 ms 12280 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 11940 KB Output is correct
2 Correct 966 ms 12272 KB Output is correct
3 Correct 1068 ms 12320 KB Output is correct
4 Correct 1162 ms 12284 KB Output is correct
5 Correct 1029 ms 12240 KB Output is correct
6 Correct 857 ms 12280 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 18 ms 296 KB Output is correct
13 Correct 505 ms 22212 KB Output is correct
14 Correct 505 ms 25732 KB Output is correct
15 Correct 617 ms 24640 KB Output is correct
16 Correct 477 ms 24956 KB Output is correct
17 Correct 797 ms 29356 KB Output is correct
18 Correct 737 ms 29204 KB Output is correct
19 Correct 801 ms 29392 KB Output is correct
20 Correct 870 ms 29168 KB Output is correct
21 Correct 830 ms 29188 KB Output is correct
22 Correct 782 ms 29336 KB Output is correct
23 Correct 748 ms 29152 KB Output is correct
24 Correct 730 ms 29236 KB Output is correct
25 Correct 1123 ms 26668 KB Output is correct
26 Correct 1060 ms 26660 KB Output is correct
27 Correct 801 ms 28748 KB Output is correct
28 Correct 1000 ms 29160 KB Output is correct
29 Correct 916 ms 28800 KB Output is correct
30 Correct 1088 ms 28836 KB Output is correct
31 Correct 964 ms 29152 KB Output is correct
32 Correct 929 ms 25440 KB Output is correct
33 Correct 7 ms 376 KB Output is correct