Submission #875349

#TimeUsernameProblemLanguageResultExecution timeMemory
875349serifefedartarVudu (COCI15_vudu)C++17
42 / 140
229 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 998244353; const ll LOGN = 20; const ll MAXN = 1e6 + 10; vector<ll> A, cc; int fen[MAXN]; int index(ll k) { return upper_bound(cc.begin(), cc.end(), k) - cc.begin(); } ll get(int k) { ll res = 0; while (k > 0) { res += fen[k]; k -= k & -k; } return res; } void add(int k, int val) { while (k < MAXN) { fen[k] += val; k += k & -k; } } int main() { fast memset(fen, 0, sizeof(fen)); int N, P; cin >> N; A = vector<ll>(N+1); for (int i = 1; i <= N; i++) { cin >> A[i]; A[i] += A[i-1]; } cin >> P; for (ll i = 1; i <= N; i++) { cc.push_back(P * i - A[i-1]); cc.push_back(P * i - A[i] + P - 1); } sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); ll ans = 0; for (ll i = 1; i <= N; i++) { add(index(P * i - A[i-1]), 1); ans += i - get(index(P * i - A[i] + P - 1)); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...