oj.uz

Submission #527663

# Submission time Handle Problem Language Result Execution time Memory
527663 2022-02-18T00:05:52 Z colazcy Vudu (COCI15_vudu) C++11
140 / 140
 221 ms 37312 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 217 ms 36080 KB Output is correct
5 Correct 121 ms 20544 KB Output is correct
6 Correct 184 ms 31896 KB Output is correct
7 Correct 199 ms 33172 KB Output is correct
8 Correct 168 ms 28808 KB Output is correct
9 Correct 221 ms 37312 KB Output is correct
10 Correct 190 ms 32348 KB Output is correct