제출 #1272122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272122		ahmd_ibraaa	Vudu (COCI15_vudu)	C++20	42 / 140	1099 ms	102716 KiB

vudu

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define medal ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define sec second
#define endl '\n'

const int maxn = 1e6+10;
int frek[maxn];
int st[4*maxn];
map<int,int> mp;

void update(int id, int l=0, int r=1e6, int node=1){
	if(l==r){
		st[node]++;
	}
	else{
		int mid = (l+r)/2;
		if(id<=mid) update(id, l, mid, node*2);
		else update(id, mid+1, r, node*2+1);
		st[node] = st[node*2]+st[node*2+1];
	}
	return;
}

int query(int A, int B, int l=0, int r=1e6, int node=1){
	if(l>B || r<A) return 0;
	if(A<=l && r<=B) return st[node];
	int mid = (l+r)/2;
	return query(A,B,l,mid,node*2) + query(A,B,mid+1,r,node*2+1);
}

signed main(){
	medal
	int n; cin>>n;
	int a[n+1]; int pref[n+1];
	pref[0] = 0;
	
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	int p; cin>>p;
	
	vector<int> vec;
	vec.push_back(0);
	for(int i=1; i<=n; i++){
		a[i]-=p;
		pref[i] = pref[i-1]+a[i];
		vec.push_back(pref[i]);
	}
	sort(vec.begin(), vec.end());
	
	for(int i=0; i<vec.size(); i++){
		mp[vec[i]] = i;
	}
	
	int ans = 0;
	update(mp[0]);
	for(int i=1; i<=n; i++){
		int num = query(0, mp[pref[i]]);
		ans += num;
		update(mp[pref[i]]);
	}
	cout<<ans;
}

• Subtask 1: 42 / 140