oj.uz

Submission #457926

# Submission time Handle Problem Language Result Execution time Memory
457926 2021-08-07T14:49:16 Z JovanB Vudu (COCI15_vudu) C++17
140 / 140
 282 ms 27724 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 1000001;

int val[N+5];
int a[N+5];

int bit[N+5];

void bit_add(int x){
    while(x <= N){
        bit[x]++;
        x += x & -x;
    }
}

int bit_get(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int p;
    cin >> p;
    vector <pair <ll, int>> vec;
    vec.push_back({0, 0});
    ll pref = 0;
    for(int i=1; i<=n; i++){
        a[i] -= p;
        pref += a[i];
        vec.push_back({pref, i});
    }
    sort(vec.begin(), vec.end());
    int trr = 0;
    for(int i=0; i<vec.size(); i++){
        if(i == 0 || vec[i].first != vec[i-1].first) trr++;
        val[vec[i].second] = trr;
    }
    bit_add(val[0]);
    ll res = 0;
    for(int i=1; i<=n; i++){
        res += bit_get(val[i]);
        bit_add(val[i]);
    }
    cout << res << "\n";
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<vec.size(); i++){
      |                  ~^~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 272 ms 26900 KB Output is correct
5 Correct 151 ms 19024 KB Output is correct
6 Correct 233 ms 23828 KB Output is correct
7 Correct 243 ms 24832 KB Output is correct
8 Correct 211 ms 21504 KB Output is correct
9 Correct 282 ms 27724 KB Output is correct
10 Correct 249 ms 24200 KB Output is correct