oj.uz

Submission #445501

# Submission time Handle Problem Language Result Execution time Memory
445501 2021-07-18T10:38:32 Z ak2006 Vudu (COCI15_vudu) C++14
140 / 140
 461 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
struct BIT
{
    int n;
    vl bit;
    BIT(int _n)
    {
        n = _n;
        bit.assign(n + 10,0);
    }
    void update(int i,ll inc)
    {
        for (;i<=n;i+=i&(-i))bit[i] += inc;
    }
    ll sum(int i)
    {
        ll ret = 0;
        for (;i>0;i-=i&(-i))ret += bit[i];
        return ret;
    }
};
int main()
{
    setIO();
    ll n,p;
    cin>>n;
    vvl a(n + 1,vl(2));
    for (int i = 1;i<=n;i++)cin>>a[i][0],a[i][1] = i;
    cin>>p;
    for (int i = 1;i<=n;i++)a[i][0] = a[i - 1][0] + a[i][0] - p;

    sort(a.begin() + 1,a.end());

    BIT val(n);
    ll out = 0;
    for (int i = 1;i<=n;i++){
        ll now = val.sum(a[i][1] - 1);
        out += now;
        val.update(a[i][1],1);
        if (a[i][0] >= 0)out++;
    }
    cout<<out;
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 461 ms 65536 KB Output is correct
5 Correct 241 ms 39804 KB Output is correct
6 Correct 410 ms 62080 KB Output is correct
7 Correct 407 ms 64600 KB Output is correct
8 Correct 364 ms 56108 KB Output is correct
9 Correct 451 ms 65536 KB Output is correct
10 Correct 385 ms 62972 KB Output is correct