Submission #939522

#	Time	Username	Problem	Language	Result	Execution time	Memory
939522		Sundavar	Distributing Candies (IOI21_candies)	C++17	8 / 100	328 ms	47248 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef pair<long long, int> plli;
struct segTree{
    struct node{
        plli mxm, mnm;
        long long lazy;
    };
    vector<node> t;
    int maxN;
    segTree(int n){
        maxN = (1<<((int)log2(n)+1));
        t.resize(2*maxN);
        for(int i = maxN; i < t.size(); i++)
            t[i].mxm = {0, i-maxN}, t[i].mnm = {0, i-maxN};
        for(int i = maxN; i > 0; i--)
            t[i].mxm = max(t[i*2].mxm, t[i*2+1].mxm), t[i].mnm = min(t[i*2].mnm, t[i*2+1].mnm);
    }

    void upd(int v, long long val){
        t[v].lazy += val, t[v].mxm.first += val, t[v].mnm.first += val;
    }

    void push(int v){
        upd(v*2, t[v].lazy), upd(v*2+1, t[v].lazy);
        t[v].lazy = 0;
    }

    void add(int pos, long long val){
        add(1, pos, maxN, 0, maxN, val);
    }

    void add(int v, int ll, int rr, int l, int r, long long val){
        if(min(r, rr) <= max(l, ll)) return;
        if(ll <= l && r <= rr){
            upd(v, val);
            return;
        }
        push(v);
        int m = (l+r)/2;
        add(v*2, ll, rr, l, m, val), add(v*2+1, ll, rr, m, r, val);
        t[v].mnm = min(t[v*2].mnm, t[v*2+1].mnm);
        t[v].mxm = max(t[v*2].mxm, t[v*2+1].mxm);
    }
    pair<plli, plli > find(long long c){
        return find(1, c, {-1e18, -1}, {1e18, -1});
    }
    pair<plli, plli > find(int v, long long c, plli mxm, plli mnm){
        if(v >= maxN) 
            return {max(mxm, t[v].mxm), min(mnm, t[v].mnm)};
        
        push(v);
        plli mxm2 = max(mxm, t[v*2+1].mxm), mnm2 = min(t[v*2+1].mnm, mnm);
        if(mxm2.first - mnm2.first >= c) return find(v*2+1, c, mxm, mnm);
        return find(2*v, c, mxm2, mnm2);    
    }

};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = l.size();
    std::vector<int> s(c.size());
    segTree t = segTree(n+2);
    t.add(0, 1e9+7), t.add(1, -1e9-7);
    vector<vector<plli> > diff(c.size()+1);
    long long sum = 0;
    for(int i = 0; i < n; i++){
        diff[l[i]].push_back({v[i], i+2});
        diff[r[i]+1].push_back({-v[i], i+2});
    }
    for(int i = 0; i < c.size(); i++){
        for(plli& a : diff[i]) t.add(a.second, a.first), sum += a.first;
        auto [mxm, mnm] = t.find(c[i]);
        // cout << mxm.first << " " << mxm.second << " " << mnm.first << " " << mnm.second << "\n";
        // cout << sum << "\n";
        if(mxm.second < mnm.second)
            s[i] = sum - mnm.first;
        else
            s[i] = c[i] - (mxm.first - sum);
    }
    return s;

}

/*int main(){
    distribute_candies({10, 15, 13}, {0, 0}, {1, 2}, {20, -11});
}*/

Compilation message (stderr)

candies.cpp: In constructor 'segTree::segTree(int)':
candies.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i = maxN; i < t.size(); i++)
      |                           ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < c.size(); i++){
      |                    ~~^~~~~~~~~~

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