oj.uz

Submission #260184

# Submission time Handle Problem Language Result Execution time Memory
260184 2020-08-09T14:12:00 Z sckmd Vudu (COCI15_vudu) C++14
140 / 140
 444 ms 29524 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MAXN 1000005
ll a[MAXN];
int bit[MAXN];
map <ll,int> mp;

void update(int idx,int val)
{
  while(idx < MAXN)
  {
    bit[idx] += val;
    idx += idx&(-idx);
  }
}
ll get(int idx)
{
  ll ret = 0LL;
  while(idx > 0)
  {
    ret += bit[idx];
    idx -= idx&(-idx);
  }
  return ret;
}
ll get(int l,int r)
{
  ll ret = get(r);
  if(l > 0)ret -= get(l-1);
  return ret;
}
vector <ll> all;
vector <ll> allz;
int main()
{
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)cin >> a[i];
  int p;
  cin >> p;
  for(int i = 1; i <= n; i++)a[i]-=p,a[i]+=a[i-1];
  allz.push_back(0);
  for(int i = 1; i <= n; i++)allz.push_back(a[i]);
  sort(allz.begin(),allz.end());
  ll prev = -1e18;
  for(auto x:allz)
  {
    if(x==prev)continue;
    all.push_back(x);
    prev=x;
  }
  ll ans = 0LL;
  for(int i = 0; i <= n; i++)
  {
    int idx = lower_bound(all.begin(),all.end(),a[i])-all.begin();
    idx++;
    ans += 1LL*get(idx);
    update(idx,1);
  }
  cout << ans;
  return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 444 ms 29016 KB Output is correct
5 Correct 251 ms 23252 KB Output is correct
6 Correct 357 ms 27988 KB Output is correct
7 Correct 418 ms 28372 KB Output is correct
8 Correct 333 ms 26964 KB Output is correct
9 Correct 432 ms 29524 KB Output is correct
10 Correct 370 ms 28300 KB Output is correct