Submission #624999

#TimeUsernameProblemLanguageResultExecution timeMemory
624999ArnchWorst Reporter 3 (JOI18_worst_reporter3)C++17
0 / 100
210 ms11036 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> #pragma GCC optimize("O3,no-stack-protector,unroll-loops") #pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl #define endl '\n' constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969; int a[N], d[N]; int T[N], L[N], R[N]; map<int, pair<int, int> > s; int main() { ios :: sync_with_stdio(0), cin.tie(0); int n, q; cin >>n >>q; for(int i = 1; i <= n; i++) cin >>a[i]; bool f = 0; for(int i = 1; i <= n; i++) { if(a[i] > 1) f = 1; } d[1] = a[1]; for(int i = 2; i <= n; i++) { if(a[i] <= a[i - 1]) { d[i] = d[i - 1]; continue; } ll cnt = a[i] / d[i - 1]; if(cnt * d[i - 1] < a[i]) cnt++; d[i] = d[i - 1] * cnt; } vector<int> vc; for(int i = 1; i <= n;) { if(d[i] > 1e9) continue; int ptr = i; while(ptr <= n && d[ptr] == d[i]) ptr++; // s[d[i]] = make_pair(i, ptr - 1); vc.push_back(d[i]); i = ptr; } if(f && n > 1000) { assert(0); } sort(All(vc)), vc.erase(unique(All(vc)), vc.end()); for(int j = 0; j < q; j++) { cin >>T[j] >>L[j] >>R[j]; int ans = 0; for(auto i : vc) { if(i > T[j]) break; int cnt = (T[j] / i) * i; int l = cnt + -s[i].second, r = cnt + -s[i].first; if(r < L[j] || l > R[j]) continue; if(r >= R[j] && l <= L[j]) { ans += R[j] - L[j] + 1; continue; } if(R[j] >= r && L[j] <= l) { ans += r - l + 1; continue; } if(r <= R[j]) ans += r - L[j] + 1; else ans += R[j] - l + 1; } cout<<ans + (T[j] >= L[j] && T[j] <= R[j]) <<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...