Submission #1243921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243921		Quentolosse	Distributing Candies (IOI21_candies)	C++20	0 / 100	370 ms	34204 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Neoud {
    int mini = 0, maxi = 0;
    int pos_min = -1, pos_max = -1;
};

struct Ret {
    bool type;
    int val;
    int pos;
};

struct Segtree {
    
    vector<Neoud> valeurs;
    vector<int> lazy;
    
    int taille = 1;
    Segtree(int n) {
        while(taille < n) {
            taille <<= 1;
        }

        valeurs.resize(2*taille);
        lazy.resize(2*taille, 0);

        for (int i = 0; i < taille; i++)
        {
            valeurs[taille + i].pos_min = i;
            valeurs[taille + i].pos_max = i;
        }
        
        for (int i = taille - 1; i >= 0; i--)
        {
            valeurs[i].pos_min = max(valeurs[2*i].pos_min, valeurs[2*i+1].pos_min);
            valeurs[i].pos_max = max(valeurs[2*i].pos_max, valeurs[2*i+1].pos_max);
        }
    }
    
    void push(int pos) {
        if (pos < taille) {
            lazy[2*pos] += lazy[pos];
            valeurs[2*pos].mini += lazy[pos];
            valeurs[2*pos].maxi += lazy[pos];

            lazy[2*pos+1] += lazy[pos];
            valeurs[2*pos+1].mini += lazy[pos];
            valeurs[2*pos+1].maxi += lazy[pos];  
        }

        lazy[pos] = 0;
    }

    int req_point(int pos) {
        point(taille + pos);
        return valeurs[taille + pos].mini;
    }

    void point(int pos) {
        if (pos != 1)
        {
            point(pos/2);
        }

        push(pos);
    }

    void update(int pos, int lr, int l, int r, int val) {
        push(pos);
        if (r <= lr) {
            return;
        }

        if (l >= lr) {
            lazy[pos] += val;
            valeurs[pos].mini += val;
            valeurs[pos].maxi += val;
        
            return;
        }

        update(2*pos, lr, l, (l+r)/2, val);
        update(2*pos + 1, lr, (l+r)/2, r, val);

        valeurs[pos].mini = min(valeurs[2*pos].mini, valeurs[2*pos+1].mini);
        if (valeurs[pos].mini == valeurs[2*pos+1].mini) {
            valeurs[pos].pos_min = valeurs[2*pos+1].pos_min;
        }
        else {
            valeurs[pos].pos_min = valeurs[2*pos].pos_min;
        }

        valeurs[pos].maxi = max(valeurs[2*pos].maxi, valeurs[2*pos+1].maxi);
        if (valeurs[pos].maxi == valeurs[2*pos+1].maxi) {
            valeurs[pos].pos_max = valeurs[2*pos+1].pos_max;
        }
        else {
            valeurs[pos].pos_max = valeurs[2*pos].pos_max;
        }
    }

    Ret requete(int pos, int mini, int maxi, int cible) {
        push(pos);
        if (pos >= taille) {
            if (valeurs[pos].mini < mini && maxi - valeurs[pos].mini >= cible) {
                maxi = max(maxi, valeurs[pos].maxi);
                return (Ret){true, maxi, pos-taille};
            }
            else {
                mini = min(mini, valeurs[pos].mini);
                return (Ret){false, mini, pos-taille};
            }
        }

        int min2 = min(mini, valeurs[2*pos+1].mini);
        int max2 = max(maxi, valeurs[2*pos+1].maxi);

        if (max2 - min2 > cible) {
            return requete(2*pos+1, mini, maxi, cible);
        }
        else {
            Ret r = requete(2*pos, min2, max2, cible);
            if (r.type) {
                if (valeurs[2*pos+1].maxi == r.val) {
                    r.pos = valeurs[2*pos+1].pos_max;
                }
            }
            else {
                if (valeurs[2*pos+1].mini == r.val) {
                    r.pos = valeurs[2*pos+1].pos_min;
                }
            }
            return r;
        }
    }
};

vector<signed> distribute_candies(vector<signed> c, vector<signed> l, vector<signed> r, vector<signed> v) {
    int n = c.size();
    int q = l.size();
    
    vector<pair<int,int>> inter;
    for (int i = 0; i < q; i++)
    {
        inter.push_back(make_pair(l[i], i));
        inter.push_back(make_pair(r[i]+1, i));
    }

    sort(inter.begin(), inter.end());

    int i_inter = 0;
    vector<signed> rep(n, 0);

    Segtree segtree(q+2);

    for (int i = 0; i < n; i++)
    {
        while(i_inter < (int)inter.size() && inter[i_inter].first <= i) {
            int val = 0;
            int j = inter[i_inter].second;
            if (inter[i_inter].first == l[j]) {
                val = v[j];
            }
            else {
                val = -v[j];
            }

            segtree.update(1, j+1, 0, segtree.taille, val);
            i_inter++;
        }

        Ret r = segtree.requete(1, 1e9, -1e9, c[i]);
        int pos = r.pos;

        if (pos == 0) {
            rep[i] = segtree.req_point(q);
        }
        else if (r.type) {
            rep[i] = c[i] - (segtree.req_point(pos) - segtree.req_point(q));
        }
        else {
            rep[i] = segtree.req_point(q) - segtree.req_point(pos);
        }
    }
    
    return rep;
    
}

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