Submission #330356

#TimeUsernameProblemLanguageResultExecution timeMemory
330356VROOM_VARUNWorst Reporter 3 (JOI18_worst_reporter3)C++14
100 / 100
671 ms29360 KiB
/* ID: varunra2 LANG: C++ TASK: reporter */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define int long long #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions VI f, d; VVI qrys; int n, q; void calc_f() { f[0] = d[0]; for (int i = 1; i <= n; i++) { f[i] = f[i - 1] * ((d[i] + f[i - 1] - 1) / f[i - 1]); } } int where(int ind, int time) { // where was person ind at time time? return (time / f[ind]) * f[ind] - ind; } bool works(int ind, int time, int pos) { if (ind > n) return true; return where(ind, time) <= pos; } int getless(int time, int pos) { // elements <= pos at time time int x = -1; for (int b = n + 1; b >= 1; b /= 2) { while (!works(x + b, time, pos)) x += b; } return n - x; } int32_t main() { // #ifndef ONLINE_JUDGE // freopen("reporter.in", "r", stdin); // freopen("reporter.out", "w", stdout); // #endif cin.sync_with_stdio(0); cin.tie(0); cin >> n >> q; f.resize(n + 1); d.resize(n + 1); for (int i = 0; i < n; i++) { cin >> d[i + 1]; } d[0] = 1; calc_f(); while (q--) { int t, l, r; cin >> t >> l >> r; int val1 = getless(t, r); int val2 = getless(t, l - 1); cout << val1 - val2 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...