Submission #946597

#TimeUsernameProblemLanguageResultExecution timeMemory
946597MohammadAbduljalilVudu (COCI15_vudu)C++17
112 / 140
516 ms65536 KiB
#include <bits/extc++.h>
#define int long long 
using namespace std; 
using namespace __gnu_pbds; 
int const mxN = 3e5+5;
int const mxN2 = 1e6;
int a[mxN2 + 5];

signed main() {
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   
   int n,p, ans = 0;
   cin>>n;
   for(int i=0; i<n; i++) cin>>a[i];
   cin>>p;
   tree<int,null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> st;
   st.insert(p);
   for(int i=0; i<n; i++) {
      a[i] += (i? a[i-1]:0);
      int x = a[i] - p*i;
      ans += st.order_of_key(x+1);
      st.insert(x);
   }
   cout<<ans;
   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...