Submission #1230182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230182		Ludissey	Distributing Candies (IOI21_candies)	C++20	29 / 100	622 ms	29356 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
 
using namespace std;

#define all(a) (a.begin(), a.end())
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define int long long


struct node{
    node* l;
    node* r;
    int mx,mn,lazy=0;
    void update(){
        if(l!=NULL) { mn=min(mn,l->mn); mx=max(mx,l->mx); }
        if(r!=NULL) { mn=min(mn,r->mn); mx=max(mx,r->mx); }
    }
};

struct segtree{
    int n;
    node* root;
    void propagate(node* x){
        if(x->l!=NULL) {
            x->l->lazy+=x->lazy;
            x->l->mn+=x->lazy;
            x->l->mx+=x->lazy;
        }
        if(x->r!=NULL) {
            x->r->lazy+=x->lazy;
            x->r->mn+=x->lazy;
            x->r->mx+=x->lazy;
        }
        x->lazy=0;
    }
    void build(node* x, int l, int r){
        if(l==r) return;
        x->l=new node{NULL,NULL,0,0,0};
        x->r=new node{NULL,NULL,0,0,0};
        int mid=(l+r)/2;
        build(x->l,l,mid);
        build(x->r,mid+1,r);
    }
    void update(node* x, int l, int r, int qL, int qR, int v){
        if(r<qL||l>qR) return;
        if(l>=qL&&r<=qR){
            x->mx+=v;
            x->mn+=v;
            x->lazy+=v;
            return;
        }
        propagate(x);
        int mid=(l+r)/2;
        update(x->l,l,mid,qL,qR,v);
        update(x->r,mid+1,r,qL,qR,v);
        x->update();
    }
    pair<int,int> query(node* x, int l, int r, int qL, int qR){
        if(r<qL||l>qR) return {1e9,-1e9};
        if(l>=qL&&r<=qR) return {x->mn,x->mx};
        propagate(x);
        int mid=(l+r)/2;
        pair<int,int> u1=query(x->l,l,mid,qL,qR);
        pair<int,int> u2=query(x->r,mid+1,r,qL,qR);
        return {min(u1.first,u2.first),max(u1.second,u2.second)};
    }
    segtree(int _n){
        n=_n;
        root=new node{NULL,NULL,0,0,0};
        build(root, 0, n-1);
    }
    void update(int l, int r, int v){
        update(root,0,n-1,l,r,v);
        return;
    }
    pair<int,int> query(int l, int r){
        return query(root,0,n-1,l,r);
    }
};

std::vector<signed> distribute_candies(std::vector<signed> _c, std::vector<signed> l, std::vector<signed> r, std::vector<signed> v) {
    int n = _c.size();
    vector<signed> s(n);
    int q=sz(l);
    segtree seg(q);
    int j=0;
    vector<pair<int,int>> sc(n);
    for (int i = 0; i < n; i++) sc[i]={_c[i],i};
    sort(rall(sc));
    for (int i = 0; i < q; i++) seg.update(i,q-1,v[i]);
    for (int i = 0; i < n; i++)
    {
        
        int c=sc[i].first;
        pair<int,int> qe=seg.query(j,q-1);
        while(qe.first<0||qe.second>c){
            int vl=-1;
            int l=j;
            int r=q-1;
            int ans=-1;
            while(l<=r){
                int mid=(l+r)/2;
                pair<int,int> qr=seg.query(j,mid);
                if(qr.first<0||qr.second>c){
                    ans=mid;
                    if(qr.first<0) vl=qr.first;
                    else if(qr.second>c) vl=qr.second;
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            j=ans;
            if(vl<0) seg.update(ans,q-1,-vl);
            else seg.update(ans,q-1,c-vl);
            qe=seg.query(j,q-1);
        }
        s[sc[i].second]=seg.query(q-1,q-1).first;
    }
        
    return s;
}

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