# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
457926 | 2021-08-07T14:49:16 Z | JovanB | Vudu (COCI15_vudu) | C++17 | 282 ms | 27724 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 1000001; int val[N+5]; int a[N+5]; int bit[N+5]; void bit_add(int x){ while(x <= N){ bit[x]++; x += x & -x; } } int bit_get(int x){ int res = 0; while(x){ res += bit[x]; x -= x & -x; } return res; } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n; cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; int p; cin >> p; vector <pair <ll, int>> vec; vec.push_back({0, 0}); ll pref = 0; for(int i=1; i<=n; i++){ a[i] -= p; pref += a[i]; vec.push_back({pref, i}); } sort(vec.begin(), vec.end()); int trr = 0; for(int i=0; i<vec.size(); i++){ if(i == 0 || vec[i].first != vec[i-1].first) trr++; val[vec[i].second] = trr; } bit_add(val[0]); ll res = 0; for(int i=1; i<=n; i++){ res += bit_get(val[i]); bit_add(val[i]); } cout << res << "\n"; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 716 KB | Output is correct |
2 | Correct | 2 ms | 604 KB | Output is correct |
3 | Correct | 2 ms | 588 KB | Output is correct |
4 | Correct | 272 ms | 26900 KB | Output is correct |
5 | Correct | 151 ms | 19024 KB | Output is correct |
6 | Correct | 233 ms | 23828 KB | Output is correct |
7 | Correct | 243 ms | 24832 KB | Output is correct |
8 | Correct | 211 ms | 21504 KB | Output is correct |
9 | Correct | 282 ms | 27724 KB | Output is correct |
10 | Correct | 249 ms | 24200 KB | Output is correct |