oj.uz

답안 #105108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105108 2019-04-10T14:49:40 Z groeneprof Vudu (COCI15_vudu) C++14
42 / 140
 383 ms 66560 KB 
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 1;
const int inf = 1e16;

struct node{
	node* child1;
	node* child2;
	int val = 0;
	node(){
		child1 = 0;
		child2 = 0;
		val = 0;
	}
	void check(){
		if(child1==0){
			child1 = new node;
			child2 = new node;
		}
	}
	int update(int i, int nval, int L = 0, int R = 2*inf){
		//P("Update "<<i<<" "<<nval<<" "<<L<<" "<<R);
		if(i<L||i>R){
			return val;
		}
		if(L == R){
			return val = val+nval;
		}
		check();
		return val = child1->update(i, nval, L, (L+R)/2ll)+child2->update(i, nval, (L+R)/2ll+1ll, R);
	}
	int query(int i, int j, int L = 0, int R = 2*inf){
		//P("query "<<i<<" "<<j<<" "<<L<<" "<<R);
		if(j<L||i>R){
			return 0;
		}
		if(i<=L&&R<=j){
			return val;
		}
		check();
		return child1->query(i, j, L, (L+R)/2ll)+child2->query(i, j, (L+R)/2ll+1ll, R);
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//cout<<(-1)/2<<endl;
	int N;
	cin>>N;
	vector<int> a(N);
	F(i, N){
		cin>>a[i];
	}
	int P;
	cin>>P;
	int sum = 0, tot= 0;
	node st;
	st.update(inf,1);
	F(i, N){
		a[i]-=P;
		sum+=a[i];
		tot+=st.query(0, sum+inf);
		//(st.query(0, sum+inf));
		st.update(sum+inf, 1);
	}
	cout<<tot;
	return 0;
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1536 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 9 ms 1152 KB Output is correct
4 Runtime error 363 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 307 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 317 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 383 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 294 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 338 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 353 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)