oj.uz

Submission #787882

# Submission time Handle Problem Language Result Execution time Memory
787882 2023-07-19T13:57:56 Z Trunkty Distributing Candies (IOI21_candies) C++17
0 / 100
 452 ms 57304 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "candies.h"

ll n,q,val;
ll arr[200005];
vector<vector<ll>> toadd[200005],torem[200005];
ll maxi[800020],mini[800020],lazy[800020];

void pushdown(ll node, ll l, ll r){
    maxi[node] += lazy[node];
    mini[node] += lazy[node];
    if(l!=r){
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(ll node, ll l, ll r, ll needl, ll needr, ll val){
    pushdown(node,l,r);
    if(l>needr or r<needl){
        return;
    }   
    else if(l>=needl and r<=needr){
        lazy[node] += val;
        pushdown(node,l,r);
    }
    else{
        ll mid = (l+r)/2;
        update(node*2,l,mid,needl,needr,val);
        update(node*2+1,mid+1,r,needl,needr,val);
        maxi[node] = max(maxi[node*2],maxi[node*2+1]);
        mini[node] = min(mini[node*2],mini[node*2+1]);
    }
}

vector<ll> query(ll node, ll l, ll r, ll currmaxi, ll currmini, ll c){
    pushdown(node,l,r);
    if(l==r){
        if(mini[node]<currmini){
            currmini = mini[node];
            return {currmini,currmaxi,1};
        }
        else{
            currmaxi = maxi[node];
            return {currmini,currmaxi,2};
        }
    }
    else{
        ll mid = (l+r)/2;
        pushdown(node*2,l,mid);
        pushdown(node*2+1,mid+1,r);
        if(max(maxi[node*2+1],currmaxi)-min(mini[node*2+1],currmini)>=c){
            return query(node*2+1,mid+1,r,currmaxi,currmini,c);
        }
        else{
            return query(node*2,l,mid,max(maxi[node*2+1],currmaxi),min(mini[node*2+1],currmini),c);
        }
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    n = c.size();
    for(ll i=1;i<=n;i++){
        arr[i] = c[i-1];
    }
    q = v.size();
    for(ll i=1;i<=q;i++){
        toadd[l[i-1]+1].push_back({v[i-1],i});
        torem[r[i-1]+2].push_back({v[i-1],i});
    }
    vector<int> ans;
    for(ll i=1;i<=n;i++){
        for(vector<ll> j:toadd[i]){
            update(1,0,n,j[1],n,j[0]);
            val += j[0];
        }
        for(vector<ll> j:torem[i]){
            update(1,0,n,j[1],n,-j[0]);
            val -= j[0];
        }
        if(maxi[1]-mini[1]<=arr[i]){
            ans.push_back(val-mini[1]);
        }
        else{
            vector<ll> qv = query(1,0,n,0,2e9,arr[i]);
            if(qv[2]==1){
                qv[0] = qv[1]-arr[i];
            }
            else{
                qv[1] = qv[0]+arr[i];
            }
            ans.push_back(val-qv[0]);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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