oj.uz

Submission #976992

# Submission time Handle Problem Language Result Execution time Memory
976992 2024-05-07T10:09:51 Z SeenSiravit Vudu (COCI15_vudu) C++14
56 / 140
 315 ms 65536 KB 
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e6 + 5;

struct DATA
{
    int idx;
    ll val;
};


int n;
ll a[mxN];
DATA b[mxN];
ll p;
int fw[mxN];
vector<DATA> tmp;
map<int,int> mp;

bool cmp(DATA x , DATA y){
    if(x.val == y.val) return x.idx < y.idx;
    return x.val < y.val;
}

void update(int idx , int val){
    for(int i=idx;i<mxN;i += (i & -i)) fw[i] += val;
}

ll query(int idx){
    ll res = 0;
    for(int i=idx;i>0;i -= (i & -i)) res += fw[i];
    return res;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    
    cin>> n;

    for(int i=1;i<=n;i++) cin>> a[i] , a[i] += a[i-1];

    // for(int i=1;i<=n;i++) cout<< a[i] << " ";
    // cout<< "\n";

    cin>> p;

    for(int i=1;i<=n;i++) b[i].val = a[i] - p*i , b[i].idx = i , tmp.push_back(b[i]);
    // for(int i=1;i<=n;i++) cout<< b[i] << " ";
    // cout<< "\n\n";

    tmp.push_back({0,0});

    sort(tmp.begin() , tmp.end() , cmp);

    // for(auto elem : tmp) cout<< elem.idx << " " << elem.val << " , ";
    // cout<< "\n";

    int id = 1;
    for(auto elem : tmp){
        mp[elem.idx] = id;
        id++;
    }

    ll ans = 0;

    for(int i=1;i<=n;i++){
        int cnt = query(mp[b[i].idx]);

        // cout<< "\ncnt = " << cnt << " ";

        if(a[i]-a[i-1] >= p) cnt++;

        // cout<< cnt << "\n\n";

        ans += cnt;

        // cout<< cnt << " ";
        
        update(mp[i-1] , 1);
    }

    cout<< ans;

    return 0;
}

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7000 KB Output is correct
2 Correct 4 ms 7004 KB Output is correct
3 Correct 3 ms 6880 KB Output is correct
4 Runtime error 311 ms 65536 KB Execution killed with signal 9
5 Correct 315 ms 58536 KB Output is correct
6 Runtime error 281 ms 65536 KB Execution killed with signal 9
7 Runtime error 293 ms 65536 KB Execution killed with signal 9
8 Runtime error 268 ms 65536 KB Execution killed with signal 9
9 Runtime error 282 ms 65536 KB Execution killed with signal 9
10 Runtime error 279 ms 65536 KB Execution killed with signal 9