# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
165427 | 2019-11-27T08:21:31 Z | Atill83 | Vudu (COCI15_vudu) | C++14 | 1000 ms | 12388 KB |
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 1e6+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n, P, a[MAXN]; vector<ll> diger; ll do_it(int l, int r){ if(l == r){ return a[l] >= P; }else{ int m = (l + r)/2; diger.clear(); ll curSm = 0; for(int j = m; j >= l; j--){ ll len = (m - j + 1); curSm += a[j]; diger.push_back(curSm - P*len); } sort(diger.begin(), diger.end()); curSm = 0; ll ans = 0; for(int j = m + 1; j <= r; j++){ curSm += a[j]; ll cur = curSm - (j - m)*P; ll cnt = diger.end() - lower_bound(diger.begin(), diger.end(), -cur); ans += cnt; } return ans + do_it(l, m) + do_it(m + 1, r); } } int main(){ #ifdef Local freopen("../IO/int.txt","r",stdin); freopen("../IO/out.txt","w",stdout); #endif scanf("%lld", &n); for(int i = 1; i <= n; i++){ scanf("%lld", a + i); } scanf("%lld", &P); printf("%lld\n", do_it(1, n)); #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 508 KB | Output is correct |
4 | Execution timed out | 1039 ms | 12248 KB | Time limit exceeded |
5 | Correct | 529 ms | 8824 KB | Output is correct |
6 | Correct | 878 ms | 11200 KB | Output is correct |
7 | Correct | 929 ms | 11576 KB | Output is correct |
8 | Correct | 770 ms | 10724 KB | Output is correct |
9 | Execution timed out | 1014 ms | 12388 KB | Time limit exceeded |
10 | Correct | 970 ms | 11492 KB | Output is correct |