oj.uz

Submission #787894

# Submission time Handle Problem Language Result Execution time Memory
787894 2023-07-19T14:04:40 Z Trunkty Distributing Candies (IOI21_candies) C++17
100 / 100
 526 ms 63124 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,q,j[1],q,j[0]);
            val += j[0];
        }
        for(vector<ll> j:torem[i]){
            update(1,0,q,j[1],q,-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,q,-2e18,2e18,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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 6 ms 10100 KB Output is correct
5 Correct 8 ms 10100 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 56516 KB Output is correct
2 Correct 486 ms 56512 KB Output is correct
3 Correct 489 ms 56440 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 292 ms 56076 KB Output is correct
3 Correct 68 ms 17364 KB Output is correct
4 Correct 468 ms 62376 KB Output is correct
5 Correct 472 ms 62792 KB Output is correct
6 Correct 469 ms 63124 KB Output is correct
7 Correct 495 ms 62468 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 117 ms 48620 KB Output is correct
4 Correct 82 ms 15524 KB Output is correct
5 Correct 206 ms 57100 KB Output is correct
6 Correct 210 ms 57784 KB Output is correct
7 Correct 208 ms 58332 KB Output is correct
8 Correct 185 ms 56924 KB Output is correct
9 Correct 212 ms 58464 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 6 ms 10100 KB Output is correct
5 Correct 8 ms 10100 KB Output is correct
6 Correct 479 ms 56516 KB Output is correct
7 Correct 486 ms 56512 KB Output is correct
8 Correct 489 ms 56440 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 292 ms 56076 KB Output is correct
11 Correct 68 ms 17364 KB Output is correct
12 Correct 468 ms 62376 KB Output is correct
13 Correct 472 ms 62792 KB Output is correct
14 Correct 469 ms 63124 KB Output is correct
15 Correct 495 ms 62468 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 117 ms 48620 KB Output is correct
19 Correct 82 ms 15524 KB Output is correct
20 Correct 206 ms 57100 KB Output is correct
21 Correct 210 ms 57784 KB Output is correct
22 Correct 208 ms 58332 KB Output is correct
23 Correct 185 ms 56924 KB Output is correct
24 Correct 212 ms 58464 KB Output is correct
25 Correct 5 ms 9708 KB Output is correct
26 Correct 56 ms 15588 KB Output is correct
27 Correct 297 ms 55772 KB Output is correct
28 Correct 458 ms 61072 KB Output is correct
29 Correct 526 ms 61476 KB Output is correct
30 Correct 480 ms 61652 KB Output is correct
31 Correct 506 ms 61896 KB Output is correct
32 Correct 466 ms 61980 KB Output is correct