Submission #47455

#TimeUsernameProblemLanguageResultExecution timeMemory
47455mirbek01Worst Reporter 3 (JOI18_worst_reporter3)C++17
7 / 100
1730 ms7604 KiB
# include <bits/stdc++.h> using namespace std; const int N = 5e5 + 2; long long n, q, d[N], p[N]; int main(){ cin >> n >> q; int cn = 0; for(int i = 1; i <= n; i ++){ cin >> d[i]; if(d[i] == 1) cn ++; } if(cn == n){ for(int i = 1; i <= q; i ++){ int t, l, r; cin >> t >> l >> r; int L = t - n, R = t; if(l > R || L > r) { cout << 0 << endl; continue; } if(l <= L && R <= r){ cout << R - L + 1 << endl; continue; } if(l <= L && L <= r){ cout << r - L + 1 << endl; continue; } if(l <= R && R <= r){ cout << R - l + 1 << endl; continue; } if(L <= l && r <= R){ cout << r - l + 1 << endl; continue; } } return 0; } for(int i = 2; i <= n; i ++){ long long lo = 1, hi = 1e9; while(hi - lo > 1){ long long md = (lo + hi) >> 1; if(d[i - 1] * md + (-(i - 1)) >= d[i]) hi = md; else lo = md; } if(d[i - 1] * lo + (-(i - 1)) >= d[i]) hi = lo; d[i] = d[i - 1] * hi + (-(i - 1)) - 1 - (-i); } for(int i = 1; i <= q; i ++){ int t, l, r; cin >> t >> l >> r; p[0] = t; for(int j = 1; j <= n; j ++){ p[j] = -j; p[j] = ((p[j - 1] - p[j] - 1) / d[j]) * d[j] + p[j]; } int cn = 0; for(int j = 0; j <= n; j ++){ // cout << p[j] << " "; if(l <= p[j] && p[j] <= r) cn ++; } // cout << endl; cout << cn << endl; } } /** 3 1 2 5 3 3 2 4 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...