제출 #787891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787891		Trunkty	사탕 분배 (IOI21_candies)	C++17	0 / 100	448 ms	56436 KiB

candies

#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,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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33