oj.uz

Submission #1022130

# Submission time Handle Problem Language Result Execution time Memory
1022130 2024-07-13T10:24:06 Z edogawa_something Distributing Candies (IOI21_candies) C++17
27 / 100
 354 ms 51980 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first 
#define S second 
const ll M=2e5+10;
ll n,c,q,sz;
struct SEGTREE{
    vector<ll>res[3];
    vector<ll>pmi,pma;
    void init(ll x){
        sz=1;
        while(sz<x)
        sz*=2;
        pmi.resize(2*sz),pma.resize(2*sz);
        res[0].resize(2*sz),res[1].resize(2*sz),res[2].resize(2*sz);
    }
    void build(ll x=0,ll lx=0,ll rx=sz){
        ll mid=((lx+rx)>>1);
        res[0][x]=0,res[1][x]=0,pmi[x]=0,pma[x]=0,res[2][x]=c;
        if(rx-lx>1){
        build(x*2+1,lx,mid),build(x*2+2,mid,rx);
        }
    }
    void update(ll i,ll v,ll x=0,ll lx=0,ll rx=sz){
        if(rx-lx==1){
            pmi[x]=pma[x]=res[0][x]=res[1][x]=res[2][x]=v;
            pmi[x]=min(pmi[x],0ll),pmi[x]=max(pmi[x],-c);
            pma[x]=max(pma[x],0ll),pma[x]=min(pma[x],c);
            res[0][x]=pma[x];
            res[2][x]=c+pmi[x];
            res[1][x]=v;
            return;
        }
        ll mid=((lx+rx)>>1);
        if(i<mid)
        update(i,v,x*2+1,lx,mid);
        else
        update(i,v,x*2+2,mid,rx);
        ll lc=x*2+1,rc=x*2+2;
        res[1][x]=res[1][lc]+res[1][rc];
        pma[x]=max(pma[lc],res[1][lc]+pma[rc]);
        pmi[x]=min(pmi[lc],res[1][lc]+pmi[rc]);
        res[0][x]=res[0][lc],res[2][x]=res[2][lc];
        if(res[0][x]+pma[rc]<c&&res[0][x]+pmi[rc]>0){
        res[0][x]+=res[1][rc];
        }
        else if(res[0][x]+pma[rc]>=c){
        res[0][x]=res[2][rc];
        }
        else{
        res[0][x]=res[0][rc];
        }
        if(res[2][x]+pma[rc]<c&&res[2][x]+pmi[rc]>0)
        res[2][x]+=res[1][rc];
        else if(res[2][x]+pma[rc]>=c)
        res[2][x]=res[2][rc];
        else
        res[2][x]=res[0][rc];
    }

}seg;
vector<pair<int,int>>ql[M],qr[M];
vector<int> distribute_candies(vector<int>cc,vector<int>l,vector<int>r,vector<int>v){
    n=cc.size(),q=v.size();
    c=cc[0];
    seg.init(q);
    seg.build();
    vector<int>ans(n);
    for(int i=0;i<q;i++){
        ql[l[i]].pb({v[i],i});
        qr[r[i]].pb({v[i],i});
    }
    for(int i=0;i<n;i++){
        if(i>0)
        for(auto it:qr[i-1])
        seg.update(it.S,0);
        for(auto it:ql[i])
        seg.update(it.S,it.F);
        ans[i]=seg.res[0][0];
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Incorrect 3 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 45140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 238 ms 43600 KB Output is correct
3 Correct 40 ms 15680 KB Output is correct
4 Correct 354 ms 51048 KB Output is correct
5 Correct 336 ms 51668 KB Output is correct
6 Correct 343 ms 51980 KB Output is correct
7 Correct 323 ms 51180 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Incorrect 3 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -