Submission #821751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
821751	2023-08-11T15:20:04 Z	dungz	Vudu (COCI15_vudu)	C++17	42 / 140	1000 ms	65536 KB

vudu

#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
int tree[4000005];
int a[1000005];
vector<int> vc;
map<int,int> danh;
int d=0;
int ans=0;
void update(int node,int l,int r,int u)
{
	if(l>u or r<u) return;
	if(l==r)
	{
		tree[node]+=1;
		return; 
	}
	int m=(l+r)/2;
	update(node*2,l,m,u);
	update(node*2+1,m+1,r,u);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int get(int node,int l,int r,int u,int v)
{
	if(l>v or r<u) return 0;
	if(l>=u and r<=v) return tree[node];
	int m=(l+r)/2;
	return get(node*2,l,m,u,v)+get(node*2+1,m+1,r,u,v);
}
int main(){

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,p;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}	
	cin>>p;
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i]+a[i-1]-p;
		vc.push_back(a[i]);
	}
	vc.push_back(0);
	sort(vc.begin(),vc.end());
	for(auto i:vc)
	{
		if(!danh[i])
		{
			danh[i]=++d;
		}
	}
	update(1,1,d,danh[0]);
	for(int i=1;i<=n;i++)
	{
		int temp=--upper_bound(vc.begin(),vc.end(),a[i])-vc.begin();
		if(temp<0) continue;
		temp=danh[vc[temp]];
		ans+=get(1,1,d,1,temp);
		update(1,1,d,danh[a[i]]);
	}
	cout<<ans;
}
/*
-1 0 0
*/

Subtask #1

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	724 KB	Output is correct
2	Correct	4 ms	724 KB	Output is correct
3	Correct	4 ms	596 KB	Output is correct
4	Execution timed out	1050 ms	65536 KB	Time limit exceeded
5	Execution timed out	1010 ms	43748 KB	Time limit exceeded
6	Execution timed out	1054 ms	63672 KB	Time limit exceeded
7	Execution timed out	1066 ms	65536 KB	Time limit exceeded
8	Execution timed out	1075 ms	58228 KB	Time limit exceeded
9	Execution timed out	1040 ms	65536 KB	Time limit exceeded
10	Execution timed out	1056 ms	64408 KB	Time limit exceeded