Submission #367143

#	Time	Username	Problem	Language	Result	Execution time	Memory
367143		cpp219	Vudu (COCI15_vudu)	C++14	140 / 140	549 ms	41488 KiB

vudu

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 69;
const ll inf = 1e9 + 7;
typedef pair<int,int> LL;
vector<ll> v;
ll n,a[N],b[N],P,bit[N];

ll Find(ll x){
    return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}

void compress(){
    sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
    for (ll i = 1;i <= n;i++) b[i] = Find(b[i]);
}

void upd(ll p,ll val){
    for (ll i = p;i < N;i += i & -i) bit[i] += val;
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}

ll Ask(ll l,ll r){
    return Get(r) - Get(l - 1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n; v.push_back(0);
    for (ll i = 1;i <= n;i++) cin>>a[i],b[i] = b[i - 1] + a[i];
    cin>>P;
    for (ll i = 1;i <= n;i++){
        b[i] -= i*P; v.push_back(b[i]);
        //cout<<b[i]<<" ";
    }
    //exit(0);
    compress(); ll now = 0,ans = 0;
    for (ll i = 1;i <= n;i++) upd(b[i],1);
    for (ll i = 1;i <= n;i++){
        ll id = Find(now);
        ans += Ask(id,N - 1); upd(b[i],-1); now += a[i] - P;
        //cout<<id; exit(0);
    }
    cout<<ans;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140