제출 #447263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447263		Habitus	Vudu (COCI15_vudu)	C++14	140 / 140	259 ms	45124 KiB

vudu

#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 / 140