oj.uz

Submission #814955

# Submission time Handle Problem Language Result Execution time Memory
814955 2023-08-08T11:23:50 Z blackyuki Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 39576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
#include "candies.h"

struct segtree{
    ll N=1;
    vi segma,segmi,lazy;
    segtree(ll n){
        while(N<n)N<<=1;
        segma=vi(N*2,-inf);segmi=vi(N*2,inf);lazy=vi(N*2);
        rep(i,n)segma[i+N]=segmi[i+N]=0;
        for(ll i=N-1;i>0;i--){
            segma[i]=max(segma[i*2],segma[i*2+1]);
            segmi[i]=min(segmi[i*2],segmi[i*2+1]);
        }
    }
    void add(ll x,ll a,ll b){
        REP(i,a,b){
            segma[i+N]+=x;
            segmi[i+N]+=x;
        }
    }
    ll getma(ll a,ll b){
        ll res=-inf;
        REP(i,a,b)chmax(res,segma[i+N]);
        return res;
    }
    ll getmi(ll a,ll b){
        ll res=inf;
        REP(i,a,b)chmin(res,segmi[i+N]);
        return res;
    }
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    ll n=c.size(),q=v.size();
    vvp event(n+1);
    rep(i,q){
        event[l[i]].pb(q-i,-v[i]);
        event[r[i]+1].pb(q-i,v[i]);
    }
    segtree seg(q+1);
    vector<int> res(n);
    rep(i,n){
        for(P x:event[i])seg.add(x.se,x.fi,q+1);
        ll ok=q+1,ng=-1;
        while(ok-ng>1){
            ll md=(ok+ng)/2;
            if(seg.getma(0,md+1)-seg.getmi(0,md+1)>=c[i])ok=md;
            else ng=md;
        }
        if(ok==q+1||seg.getma(0,ok+1)==seg.getma(ok,ok+1))res[i]=-seg.getmi(0,ok+1);
        else res[i]=c[i]-seg.getma(0,ok+1);
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 584 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 21 ms 596 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 39576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5071 ms 29212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 5059 ms 26404 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 584 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 21 ms 596 KB Output is correct
6 Execution timed out 5058 ms 39576 KB Time limit exceeded
7 Halted 0 ms 0 KB -