oj.uz

Submission #218548

# Submission time Handle Problem Language Result Execution time Memory
218548 2020-04-02T09:22:15 Z socho Vudu (COCI15_vudu) C++14
14 / 140
 842 ms 33432 KB 
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double

const int N = 2000005;
long long fw[N];
void update(int x, int v) {
    for (; x<N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}

int qry(int x) {
	if (x <= 0) return 0;
	int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}

int qry(int a, int b) {
	return qry(b+1);
}

void upd(int x, int v) {
	x++;
	for (; x<N; x+=x&(-x)) fw[x] += v; 
}

signed main() {
	
	int n;
	cin >> n;
	long long arr[n];
	for (int i=0; i<n; i++) cin >> arr[i];
	int p;
	cin >> p;
	
	for (int i=0; i<n; i++) arr[i] -= p;
	
	long long pf[n];
	pf[0] = arr[0];
	for (int i=1; i<n; i++) pf[i] = pf[i-1] + arr[i];
	
	sort(pf, pf+n);
	
	long long sm = 0;
	long long ans = 0;
	
	for (int i=0; i<n; i++) {
		if (pf[i] >= 0) ans++;
	}
	
	for (int i=0; i<n; i++) {
		sm += arr[i];
		int low = lower_bound(pf, pf+n, sm) - pf;
		ans += qry(0, low);
		// cout << i << '>' << ans << endl; 
		upd(low, qry(low, low)-qry(low-1, low-1)+1);
	}
	
	cout << ans;
	
}

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 512 KB Output isn't correct
2 Incorrect 7 ms 512 KB Output isn't correct
3 Incorrect 7 ms 512 KB Output isn't correct
4 Incorrect 842 ms 32376 KB Output isn't correct
5 Incorrect 458 ms 13560 KB Output isn't correct
6 Correct 723 ms 28796 KB Output is correct
7 Incorrect 742 ms 29944 KB Output isn't correct
8 Incorrect 646 ms 25976 KB Output isn't correct
9 Incorrect 840 ms 33432 KB Output isn't correct
10 Incorrect 739 ms 29192 KB Output isn't correct