Submission #873520

#	Time	Username	Problem	Language	Result	Execution time	Memory
873520		teo_thrash	Vudu (COCI15_vudu)	C++14	140 / 140	482 ms	43196 KiB

vudu

// it is your desire to work hard

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=1e6+3;
const int mod=1e9+7;

int n, p;
ll a[maxn];
vector<pair<ll, int>> c;

int tree[4*maxn];

void update(int x, int l, int r, int idx){
    if(l>idx or r<idx) return;

    if(l==r){
        tree[x]++;
        return ;
    }
    int m=(l+r)/2;

    update(x*2, l, m, idx);
    update(x*2+1, m+1, r, idx);

    tree[x] = tree[x*2] + tree[x*2+1];

    return ;
}

ll query(int x, int l, int r, int ql, int qr){
    if(l>qr or r<ql) return 0;

    if(ql<=l and r<=qr){
        return tree[x];
    }

    ll ans=0;
    int m=(l+r)/2;
    if(ql<=m) ans+=query(x*2, l, m, ql, qr);
    if(qr>m) ans+=query(x*2+1, m+1, r, ql, qr);

    return ans;
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

a[0]=0;
c.pb({0, 0});

cin>>n;
for(int i=1; i<=n; i++){
    cin>>a[i];
}
cin>>p;

for(int i=1; i<=n; i++){
    a[i]+=a[i-1]-p;
    c.pb({a[i], i});
}

sort(c.begin(), c.end());


int idx=0;
for(int i=0; i<c.size(); i++){
    if(i!=0){
        if(c[i].first==c[i-1].first) idx--;
    }
    a[c[i].second] = idx;
    idx++;
}

ll nas=0;
update(1, 0, n, a[0]);
for(int i=1; i<=n; i++){
    nas+=query(1, 0, n, 0, a[i]);
    update(1, 0, n, a[i]);
}
cout<<nas;

return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:76:15: 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]
   76 | for(int i=0; i<c.size(); i++){
      |              ~^~~~~~~~~

• Subtask 1: 140 / 140