Submission #508745

#	Time	Username	Problem	Language	Result	Execution time	Memory
508745		sumit_kk10	Vudu (COCI15_vudu)	C++17	140 / 140	268 ms	43700 KiB

vudu

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define pb push_back
#define F first 
#define S second
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
long long n, k, a[N], ans, pre[N], fenwick[N];

void upd(int node, int val){
	for(int i = node; i < N; i += (i & -i))
		fenwick[i] += val;
}

int get(int node){
	int ans = 0;
	for(int i = node; i >= 1; i -= (i & -i))
		ans += fenwick[i];
	return ans;
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	cin >> k;
	vector<pair<long long, int> > val;
	val.pb({0, 0});
	for(int i = 1; i <= n; ++i)
		val.push_back({pre[i] - i * k, i});
	sort(val.begin(), val.end());
	vector<int> work(n + 1);
	int ct = 1;
	work[val[0].S] = ct;
	for(int i = 1; i <= n; ++i){
		if(val[i].F == val[i - 1].F)
			work[val[i].S] = ct;
		else{
			++ct;
			work[val[i].S] = ct;
		}
	}
	upd(work[n], 1);
	for(int i = n - 1; i >= 0; --i){
		ans += get(N - 1) - get(work[i] - 1);
		upd(work[i],  1);
	}
	cout << ans << '\n';
}

int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
    	solve();
	return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:58:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   58 |     while(t--)
      |     ^~~~~
vudu.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   60 |  return 0;
      |  ^~~~~~

• Subtask 1: 140 / 140