# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
463702 | 2021-08-11T14:14:12 Z | Hamed5001 | Vudu (COCI15_vudu) | C++14 | 1000 ms | 65540 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; unordered_map<ll, ll> ID; const int mxN = 1e6+100; ll BIT[mxN], N, P, id = 1; void add(int idx, ll delta) { for (; idx < id; idx += idx & -idx) BIT[idx] += delta; } ll query(int idx) { ll ret = 0; for (; idx > 0; idx -= idx & -idx) ret += BIT[idx]; return ret; } void solve() { cin >> N; vector<ll> A(N); for (auto& a : A) scanf("%lld", &a); cin >> P; for (auto& a : A) a-=P; vector<ll> AA; ll sum = 0; AA.push_back(sum); for (auto& a : A) { sum += a; AA.push_back(sum); } sort(AA.rbegin(), AA.rend()); for (int i = 0; i < AA.size(); ++i) { if (!ID[AA[i]]) ID[AA[i]] = id++; } for (auto& aa : AA) { add(ID[aa], 1); } add(ID[0], -1); sum = 0; ll ans = 0; for (auto a : A) { ans += query(ID[sum]); sum += a; add(ID[sum], -1); } printf("%lld", ans); } int main() { solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 716 KB | Output is correct |
2 | Correct | 3 ms | 716 KB | Output is correct |
3 | Correct | 3 ms | 588 KB | Output is correct |
4 | Execution timed out | 1089 ms | 64584 KB | Time limit exceeded |
5 | Correct | 682 ms | 35868 KB | Output is correct |
6 | Execution timed out | 1092 ms | 58412 KB | Time limit exceeded |
7 | Execution timed out | 1093 ms | 60344 KB | Time limit exceeded |
8 | Execution timed out | 1068 ms | 53852 KB | Time limit exceeded |
9 | Runtime error | 893 ms | 65540 KB | Execution killed with signal 9 |
10 | Execution timed out | 1091 ms | 59072 KB | Time limit exceeded |