제출 #827134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827134		ttamx	사탕 분배 (IOI21_candies)	C++17	100 / 100	441 ms	49708 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int inf=1e9;
const ll inf2=1e18;

typedef pair<ll,int> p2;

const int N=2e5+5;
const int K=1<<19;

int n,q;
vector<p2> qr[N];

struct segtree{
    struct node{
        p2 mn,mx;
        node(ll val=0,int id=0):mn(val,id),mx(val,id){}
        node(ll mn,ll mx,int id):mn(mn,id),mx(mx,id){}
        node& operator+=(const ll &o){
            mn.first+=o;
            mx.first+=o;
            return *this;
        }
        friend node operator+(node a,node b){
            node c;
            c.mn=min(a.mn,b.mn);
            c.mx=max(a.mx,b.mx);
            return c;
        }
    }t[K];
    ll lz[K];
    void pushlz(int l,int r,int i){
        t[i]+=lz[i];
        if(l<r){
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
        }
        lz[i]=0;
    }
    void build(int l,int r,int i){
        if(l==r)return void(t[i]=node(0,l));
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=t[i*2]+t[i*2+1];
    }
    void build(){
        build(1,q,1);
    }
    void update(int l,int r,int i,int x,int y,ll v){
        pushlz(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=v,pushlz(l,r,i),void();
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,int y,ll v){
        update(1,q,1,x,y,v);
    }
    node query(int l,int r,int i,ll c,node res){
        if(l==r)return t[i]+res;
        int m=(l+r)/2;
        pushlz(l,m,i*2);
        pushlz(m+1,r,i*2+1);
        auto res2=res+t[i*2+1];
        if(res2.mx.first-res2.mn.first>=c)return query(m+1,r,i*2+1,c,res);
        return query(l,m,i*2,c,res2);
    }
    node query(ll c){
        return query(1,q,1,c,node(inf2,-inf2,0));
    }
}s;

vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v) {
    n=c.size();
    q=l.size()+2;
    vector<int> ans(n);
    ll sum=0;
    s.build();
    s.update(1,q,inf);
    s.update(2,q,-inf);
    for(int i=0;i<q-2;i++){
        qr[l[i]].emplace_back(v[i],i+3);
        qr[r[i]+1].emplace_back(-v[i],i+3);
    }
    for(int i=0;i<n;i++){
        for(auto [val,id]:qr[i]){
            sum+=val;
            s.update(id,q,val);
        }
        auto tmp=s.query(c[i]);
        if(tmp.mx.second>tmp.mn.second)ans[i]=sum-(tmp.mx.first-c[i]);
        else ans[i]=sum-tmp.mn.first;
    }
    return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33