# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
165489 | 2019-11-27T11:31:29 Z | egekabas | Vudu (COCI15_vudu) | C++14 | 1000 ms | 65540 KB |
#include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<ll, ll> pii; typedef pair<ld, ld> pld; ll n, p; int a[1000009]; set<ll> s; map<ll, ll> mpp; ll cur = 1; int bit[1000009]; void upd(ll idx){ while(idx > 0){ bit[idx]++; idx -= idx&(-idx); } } ll get(ll idx){ ll ret = 0; while(idx <= cur+2){ ret += bit[idx]; idx += idx&(-idx); } return ret; } int main() { //freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%lld", &n); for(ll i = 0; i < n; ++i){ scanf("%lld", &a[i]); } scanf("%lld", &p); for(ll i = 0; i < n; ++i){ a[i] -= p; } ll add = 0; for(ll i = 0; i < n; ++i){ s.insert(-a[i]+add); add -= a[i]; s.insert(a[i]+add); } for(auto u : s){ mpp[u] = cur++; } ll ans = 0; add = 0; for(ll i = 0; i < n; ++i){ if(a[i] >= 0){ ++ans; } ans += get(mpp[-a[i]+add]); add -= a[i]; upd(mpp[a[i]+add]); } printf("%lld", ans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 1144 KB | Output is correct |
2 | Correct | 7 ms | 1016 KB | Output is correct |
3 | Correct | 6 ms | 984 KB | Output is correct |
4 | Runtime error | 897 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
5 | Execution timed out | 1086 ms | 64648 KB | Time limit exceeded |
6 | Runtime error | 727 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
7 | Runtime error | 680 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
8 | Runtime error | 675 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
9 | Runtime error | 760 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
10 | Runtime error | 716 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |