oj.uz

Submission #218545

# Submission time Handle Problem Language Result Execution time Memory
218545 2020-04-02T09:17:54 Z socho Vudu (COCI15_vudu) C++14
56 / 140
 880 ms 65540 KB 
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double

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;
	long long 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;
	
	long long 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);
	
	long long sm = 0;
	long long 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
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1280 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Correct 10 ms 1024 KB Output is correct
4 Runtime error 708 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Correct 880 ms 65536 KB Output is correct
6 Runtime error 647 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 657 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 580 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 724 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 651 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)