Submission #218544

#	Time	Username	Problem	Language	Result	Execution time	Memory
218544		socho	Vudu (COCI15_vudu)	C++14	42 / 140	725 ms	65540 KiB

vudu

#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double
#define int long long

struct node {

   int s, e, m, val;
   node *l, *r;
   node (int _s, int _e) {
       s = _s;
       e = _e;
       m = (s + e)/2;
       val = 0;
       if (s == e) return;
       l = new node(s, m);
       r = new node(m+1, e);
   }

   void upd(int p, int v) {
       if (s == p && s== e) {
           val = v;
           return;
       }
       if (p <= m) {
           l->upd(p, v);
       }
       else {
           r->upd(p, v);
       }
       val = l->val + r->val; // transition
   }

   int qry(int qs, int qe) {
       if (qs <= s && e <= qe) {
           return val;
       }
       else if (qs > e || s > qe) {
           return 0; // base case
       }
       else {
           return l->qry(qs, qe) + r->qry(qs, qe); // transition
       }
   }
} *root;

signed main() {
	
	int n;
	cin >> n;
	int arr[n];
	for (int i=0; i<n; i++) cin >> arr[i];
	int p;
	cin >> p;
	
	for (int i=0; i<n; i++) arr[i] -= p;
	
	int pf[n];
	pf[0] = arr[0];
	for (int i=1; i<n; i++) pf[i] = pf[i-1] + arr[i];
	
	sort(pf, pf+n);
	root = new node(0, n);
	
	int sm = 0;
	int ans = 0;
	
	for (int i=0; i<n; i++) {
		if (pf[i] >= 0) ans++;
	}
	
	for (int i=0; i<n; i++) {
		sm += arr[i];
		int low = lower_bound(pf, pf+n, sm) - pf;
		ans += root->qry(0, low);
		// cout << i << '>' << ans << endl; 
		root->upd(low, root->qry(low, low)+1);
	}
	
	cout << ans;
	
}

• Subtask 1: 42 / 140