oj.uz

Submission #447263

# Submission time Handle Problem Language Result Execution time Memory
447263 2021-07-25T15:47:54 Z Habitus Vudu (COCI15_vudu) C++14
140 / 140
 259 ms 45124 KB 
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

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

int n, dokle;
ll a[1000010], p;
pll pref[1000010];
ll sta[1000010];
int fwt[1000010];
void upd(int x) {
    for(; x<=dokle; x+=x&(-x)) {
        ++fwt[x];
    }
}
int query(int x) {
    int suma=0;
    for(; x>0; x-=x&(-x)) {
        suma+=fwt[x];
    }
    return suma;
}
int main() {
    ios;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i];
    }
    cin >> p;
    for(int i=1; i<=n; ++i) {
        pref[i].xx=pref[i-1].xx+a[i]-p;
        pref[i].yy=i;
    }
    sort(pref, pref+n+1);
    sta[pref[0].yy]=1;
    dokle=1;
    for(int i=1; i<=n; ++i) {
        sta[pref[i].yy]=sta[pref[i-1].yy];
        if(pref[i].xx!=pref[i-1].xx) {++sta[pref[i].yy]; ++dokle;}
    }
    ll uk=0LL;
    for(int i=0; i<=n; ++i) {
        uk+=(ll)query(sta[i]);
        upd(sta[i]);
    }
    cout << uk;
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 259 ms 43624 KB Output is correct
5 Correct 139 ms 24752 KB Output is correct
6 Correct 220 ms 38712 KB Output is correct
7 Correct 231 ms 40188 KB Output is correct
8 Correct 205 ms 34956 KB Output is correct
9 Correct 258 ms 45124 KB Output is correct
10 Correct 228 ms 39292 KB Output is correct