Submission #47459

#TimeUsernameProblemLanguageResultExecution timeMemory
47459TalantWorst Reporter 3 (JOI18_worst_reporter3)C++17
12 / 100
2082 ms10748 KiB
#include <bits/stdc++.h> #define mk make_pair #define sc second #define fr first #define pb emplace_back #define all(s) s.begin(), s.end() #define sz(s) ( (int)s.size() ) #define int long long using namespace std; const int inf = (int)1e18 + 7; const int N = (int)6e5 + 7; int n,q,d[N],a[N]; int t,L,R; int cnt; bool check (int x) { int o = floor(t / a[x]) * a[x] - x; if (L <= o) return true; return false; } bool f(int x) { int o = floor(t / a[x]) * a[x] - x; if (R >= o) return true; return false; } main () { scanf ("%lld%lld", &n,&q); for (int i = 1; i <= n; i ++) scanf ("%lld", &d[i]); for (int i = 1; i <= n; i ++) { if (i == 1) a[i] = d[i]; else { int l = 1,r = inf; while (r - l > 1) { int m = (r + l) >> 1; int o = floor(m / a[i - 1]) * a[i - 1] - (i - 1); if (o >= d[i] + 1 + (-i)) r = m; else l = m; } int o = floor(l / a[i - 1]) * a[i - 1] - (i - 1); if (o >= d[i] + 1 + (-i)) r = l; a[i] = r; } } while (q --) { scanf ("%lld%lld%lld", &t,&L,&R); if (t < L) { puts("0"); continue; } int l = 1,r = n; while (r - l > 1) { int m = (r + l) >> 1; if (check(m)) l = m; else r = m; } if (check(r)) l = r; if (!check(l)) l = 0; if (l == 0 && t <= R) { puts("1"); continue; } if (l == 0) { puts("0"); continue; } int lo = 1,hi = l; while (hi - lo > 1) { int m = (hi + lo) >> 1; if (f(m)) hi = m; else lo = m; } if (!f(hi)) { puts("0"); continue; } if (f(lo)) hi = lo; if (L <= t && t <= R) printf("%lld\n", l - hi + 2); else printf("%lld\n", l - hi + 1); } }

Compilation message (stderr)

worst_reporter3.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%lld%lld", &n,&q);
       ~~~~~~^~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:36:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%lld", &d[i]);
             ~~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:58:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%lld%lld%lld", &t,&L,&R);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...