oj.uz

Submission #508745

# Submission time Handle Problem Language Result Execution time Memory
508745 2022-01-13T16:58:13 Z sumit_kk10 Vudu (COCI15_vudu) C++17
140 / 140
 268 ms 43700 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 832 KB Output is correct
2 Correct 2 ms 648 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 268 ms 42260 KB Output is correct
5 Correct 148 ms 25648 KB Output is correct
6 Correct 224 ms 37440 KB Output is correct
7 Correct 244 ms 39024 KB Output is correct
8 Correct 200 ms 34080 KB Output is correct
9 Correct 250 ms 43700 KB Output is correct
10 Correct 229 ms 38028 KB Output is correct