oj.uz

답안 #219228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219228 2020-04-04T16:10:09 Z gabrc52 Vudu (COCI15_vudu) C++14
42 / 140
 688 ms 35960 KB 
#include <iostream>
#include <cassert>
#include <algorithm>

using namespace std;
typedef long long ll;

const int MAXN=1e6;
int N;
int arr[MAXN];
int P;
ll ac[MAXN];
ll sum[MAXN];
ll dif[MAXN];
ll sorted[MAXN];
ll than;
ll ans;
ll st[4*MAXN];

void update(int node, int L, int R, int l, int r, int val) {
	if (R < l || L > r) {
		return;
	}
	if (L >= l && R <= r) {
		st[node] += val;
		return;
	}
	int c1=node*2, c2=c1+1, M=L+(R-L)/2;
	update(c1,L,M,l,r,val);
	update(c2,M+1,R,l,r,val);
}

// how many have been deleted?
int get(int node, int L, int R, int pos) {
	if (L == R) {
		return st[node];
	}
	int c1=node*2, c2=c1+1, M=L+(R-L)/2;
	if (pos <= M) {
		return st[node] + get(c1,L,M,pos);
	} else {
		return st[node] + get(c2,M+1,R,pos);
	}
}

void remove(int val) {
	int lb = lower_bound(sorted,sorted+N,val) - sorted;
	update(1,0,N-1,lb,N-1,1);
}

int countLowerOrEqual(int val) {
	int ub = upper_bound(sorted,sorted+N,val) - sorted;
	return ub - get(1,0,N-1,ub-1);
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>N;
	for (int i=0; i<N; i++) {
		cin>>arr[i];
	}
	cin>>P;
	ac[0] = arr[0];
	for (int i=1; i<N; i++) {
		ac[i] = arr[i] + ac[i-1];
	}
	sum[0] = P;
	sorted[0] = dif[0] = sum[0] - ac[0];
	for (int i=1; i<=N; i++) {
		sum[i] = sum[i-1] + P;
		sorted[i] = dif[i] = sum[i] - ac[i];
	}
	sort(sorted, sorted+N);
	than = 0;
	ans += countLowerOrEqual(0);
	for (int i=1; i<N; i++) {
		remove(dif[i-1]);
		than += P - arr[i-1];
		ans += countLowerOrEqual(than);
	}
	cout<<ans<<'\n';
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Incorrect 611 ms 34680 KB Output isn't correct
5 Incorrect 391 ms 20600 KB Output isn't correct
6 Incorrect 586 ms 30840 KB Output isn't correct
7 Incorrect 531 ms 31840 KB Output isn't correct
8 Incorrect 417 ms 27640 KB Output isn't correct
9 Incorrect 688 ms 35960 KB Output isn't correct
10 Incorrect 609 ms 31352 KB Output isn't correct