oj.uz

Submission #873520

# Submission time Handle Problem Language Result Execution time Memory
873520 2023-11-15T08:52:54 Z teo_thrash Vudu (COCI15_vudu) C++14
140 / 140
 482 ms 43196 KB 
// 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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 482 ms 42452 KB Output is correct
5 Correct 234 ms 29108 KB Output is correct
6 Correct 377 ms 39088 KB Output is correct
7 Correct 382 ms 40980 KB Output is correct
8 Correct 335 ms 36780 KB Output is correct
9 Correct 442 ms 43196 KB Output is correct
10 Correct 410 ms 39532 KB Output is correct