oj.uz

답안 #260176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260176 2020-08-09T13:54:14 Z sckmd Vudu (COCI15_vudu) C++14
0 / 140
 347 ms 25824 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;
}

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];
  vector <int> all;
  all.push_back(0);
  for(int i = 1; i <= n; i++)all.push_back(a[i]);
  sort(all.begin(),all.end());
  all.erase(unique(all.begin(),all.end()),all.end());
  int ze = -1;
  for(int i = 0; i < all.size(); i++)if(all[i]==0){ze=i;break;}
  update(ze,1);
  ll ans = 0LL;
  for(int i = 1; i <= n; i++)
  {
    int idx = lower_bound(all.begin(),all.end(),a[i])-all.begin()+1;
    ans += 1LL*get(idx);
    update(idx,1);
  }
  cout << ans;
  return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < all.size(); i++)if(all[i]==0){ze=i;break;}
                  ~~^~~~~~~~~~~~

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Incorrect 344 ms 24800 KB Output isn't correct
5 Incorrect 197 ms 14304 KB Output isn't correct
6 Incorrect 293 ms 22112 KB Output isn't correct
7 Incorrect 315 ms 22752 KB Output isn't correct
8 Incorrect 263 ms 18500 KB Output isn't correct
9 Incorrect 347 ms 25824 KB Output isn't correct
10 Incorrect 315 ms 22496 KB Output isn't correct