Submission #457926

#	Time	Username	Problem	Language	Result	Execution time	Memory
457926		JovanB	Vudu (COCI15_vudu)	C++17	140 / 140	282 ms	27724 KiB

vudu

#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 (stderr)

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 / 140