Submission #527663

#	Time	Username	Problem	Language	Result	Execution time	Memory
527663		colazcy	Vudu (COCI15_vudu)	C++11	140 / 140	221 ms	37312 KiB

vudu

#include <cstdio>
#include <algorithm>
#include <utility>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e6 + 10;

int n,p;
ll sum[maxn],ans;
std::pair<ll,int> pir[maxn];
namespace fenwick{
	int f[maxn];
	constexpr int lowbit(const int x){return x & (-x);}
	void add(int pos,const int v){
		while(pos <= n + 1){
			f[pos] += v;
			pos += lowbit(pos);
		}
	}
	int query(int pos){
		int res = 0;
		while(pos){
			res += f[pos];
			pos -= lowbit(pos);
		}
		return res;
	}
}
int main(){
	// std::freopen("vudu.in","r",stdin);
	// std::freopen("vudu.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,1,n)std::scanf("%lld",sum + i),sum[i] += sum[i - 1];
	std::scanf("%d",&p);

	rep(i,0,n)
		pir[i].first = sum[i] - 1ll * p * i,
		pir[i].second = i;
	std::sort(pir,pir + n + 1);
	rep(i,0,n){
		ans += fenwick::query(pir[i].second + 1);
		fenwick::add(pir[i].second + 1,1);
	}
	std::printf("%lld\n",ans);
	std::fclose(stdin);
	std::fclose(stdout);	
	return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:38:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
vudu.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  rep(i,1,n)std::scanf("%lld",sum + i),sum[i] += sum[i - 1];
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~
vudu.cpp:40:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  std::scanf("%d",&p);
      |  ~~~~~~~~~~^~~~~~~~~

• Subtask 1: 140 / 140