oj.uz

Submission #367143

# Submission time Handle Problem Language Result Execution time Memory
367143 2021-02-16T10:54:18 Z cpp219 Vudu (COCI15_vudu) C++14
140 / 140
 549 ms 41488 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 549 ms 40144 KB Output is correct
5 Correct 296 ms 22992 KB Output is correct
6 Correct 459 ms 35536 KB Output is correct
7 Correct 447 ms 37072 KB Output is correct
8 Correct 403 ms 32208 KB Output is correct
9 Correct 523 ms 41488 KB Output is correct
10 Correct 451 ms 36176 KB Output is correct