oj.uz

Submission #947548

# Submission time Handle Problem Language Result Execution time Memory
947548 2024-03-16T11:33:26 Z goduadzesaba Vudu (COCI15_vudu) C++17
42 / 140
 545 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,a[N],p,x,f[N],anss;
map <int,int> mp; set <int> s;
void upd(int ind,int val){
	for (int i=ind; i<N; i+=i&(-i))
		f[i]+=val;
}
int get(int ind){
	int ans=0;
	for (int i=ind; i>0; i-=i&(-i))
		ans+=f[i];
	return ans;
}
signed main(){
	cin>>n;
	for (int i=1; i<=n; i++)
		cin>>a[i];
	cin>>p; s.insert(0);
	for (int i=1; i<=n; i++){
		a[i]-=p; a[i]+=a[i-1];
		s.insert(a[i]);
	}
	for (int it:s){
		x++; mp[it]=x;
	}
	upd(mp[0],1);
	for (int i=1; i<=n; i++){
		a[i]=mp[a[i]];
		anss+=get(a[i]);
		upd(a[i],1);
	}
	cout<<anss;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7260 KB Output is correct
2 Correct 4 ms 7260 KB Output is correct
3 Correct 4 ms 7004 KB Output is correct
4 Runtime error 545 ms 65536 KB Execution killed with signal 9
5 Runtime error 346 ms 65536 KB Execution killed with signal 9
6 Runtime error 451 ms 65536 KB Execution killed with signal 9
7 Runtime error 445 ms 65536 KB Execution killed with signal 9
8 Runtime error 423 ms 65536 KB Execution killed with signal 9
9 Runtime error 519 ms 65536 KB Execution killed with signal 9
10 Runtime error 438 ms 65536 KB Execution killed with signal 9