Submission #435368

#	Time	Username	Problem	Language	Result	Execution time	Memory
435368		mohammad_kilani	Distributing Candies (IOI21_candies)	C++17	100 / 100	4080 ms	46840 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

vector< int > add[N] , rem[N];

int n , m;

long long lazy[4 * N] ;

struct S{
    long long mn , mx;
    int mnIdx , mxIdx;
    S(long long mn,long long mx){this->mn = mn, this->mx = mx;}
    S(){mn = mx = 0;}
    void make(const S & l , const S & r){
        if(l.mn < r.mn)
            mn = l.mn , mnIdx = l.mnIdx;
        else
            mn = r.mn , mnIdx = r.mnIdx;

        if(r.mx >= l.mx)
            mx = r.mx , mxIdx = r.mxIdx;
        else
            mx = l.mx , mxIdx = l.mxIdx;
    }

} seg[4 * N];

void fix(int s,int e,int idx){
    seg[idx].mn += lazy[idx];
    seg[idx].mx += lazy[idx];
    if(s != e){
        lazy[(idx << 1)] += lazy[idx];
        lazy[(idx << 1) + 1] += lazy[idx];
    }
    lazy[idx] = 0;
}

int l , r , val;

void build(int s,int e, int idx){
    lazy[idx] = 0;
    if(s == e){
        seg[idx].mn = seg[idx].mx = 0;
        seg[idx].mnIdx = seg[idx].mxIdx = s;
        return;
    }
    build(s , ((s+e) >> 1),(idx << 1));
    build(((s+e) >> 1) + 1,e,(idx << 1) + 1);
    seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}

void update(int s,int e,int idx){
    if(lazy[idx]) fix(s , e,  idx);
    if(s > r || e < l)
        return;
    if(s >= l && e <= r){
        lazy[idx] += val;
        fix(s , e,  idx);
        return;
    }
    update(s , (s + e) >> 1 , (idx << 1));
    update(((s+e) >> 1) + 1, e , (idx << 1) + 1);
    seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}



 void getMx(int s,int e, int idx,long long &mxVal,int &mxIdx){
     if(lazy[idx]) fix(s , e,  idx);
     if(s > r || e < l)
        return;
     if(s >= l && e <= r){
        if(seg[idx].mx >= mxVal){
            mxVal = seg[idx].mx;
            mxIdx = seg[idx].mxIdx;
        }
        return;
     }
    getMx(s , ((s+e) >> 1),(idx << 1) , mxVal , mxIdx);
    getMx(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mxVal , mxIdx);
}

void getMn(int s,int e,int idx,long long& mnVal, int& mnIdx){
    if(lazy[idx]) fix(s , e , idx);
    if(s > r || e < l)
        return;
    if(s >= l && e <= r){
        if(seg[idx].mn <= mnVal){
            mnVal = seg[idx].mn;
            mnIdx = seg[idx].mnIdx;
        }
        return;
    }
    getMn(s , ((s+e) >> 1),(idx << 1) , mnVal , mnIdx);
    getMn(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mnVal , mnIdx);
}

bool getFirstMn(int s,int e,int idx,long long &mnVal,int &mnIdx ,long long val){
    //cout << s << " " << e << " " << idx  << " " << l << " " << r << endl;
    if(lazy[idx]) fix(s , e , idx);
    if(s > r || e < l)
        return false;
    if(s >= l && e <= r){
        //cout << "okay here ? " << s << " " << e << " " << seg[idx].mn << endl;
        if(seg[idx].mn >= val) return false;
        if(s == e){
            mnVal = seg[idx].mn;
            mnIdx = seg[idx].mnIdx;
            return true;
        }
        if(lazy[(idx << 1) + 1]) fix(((s+e) >> 1) + 1 , e , (idx << 1) + 1);
        if(seg[(idx << 1) + 1].mn < val)
            return getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val);
        return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);

    }
    if(getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val))
        return true;
    return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);
}



int solve(int c){
    //cout << "----------------------------------------" << endl;
    //cout << "solve " << c << endl;
    long long mnVal , curMn , mxVal;
    int mnIdx , curIdx , mxIdx;

    l = 0 , r = m - 1;
    mnVal = (long long)1e18;
    getMn(0 , m - 1 , 1,  mnVal , mnIdx);

    //cout << mnIdx << " " << mnVal << endl;

    int low = mnIdx + 1 , high = m - 1 , res = mnIdx , mid;

    while(low <= high){
        mid = (low + high) / 2;

        //cout << "check " << mid << endl;

        l = mid , r = m - 1;
        curMn = (long long)1e18;
        getMn(0 , m - 1 , 1 , curMn , curIdx);

        //cout << "curMn =" << " " << curMn << " " << curIdx << endl;

        l = mnIdx , r = curIdx;
        if(!getFirstMn(0 , m - 1 , 1,  curMn , curIdx , curMn)) cout << "what!!!?" << endl;

        //cout << "one step to left " << curMn << " " << curIdx << " " << l << " " << r << endl;

        l = curIdx , r = m - 1;
        mxVal = -(long long)1e18;
        getMx(0 , m - 1 , 1 , mxVal , mxIdx);
        l = mxIdx , r = m - 1;
        curMn = (long long)1e18;
        getMn(0 , m - 1 , 1 , curMn , curIdx);

        //cout << "check " << mid << endl;

        //cout << mxIdx << " " << curIdx << " " << curMn << " " << mxVal << endl;

        if(curIdx == mxIdx || (curMn + c - mxVal) >= 0)
            high = mid - 1;
        else
            res = mid , low = mid + 1;
    }

    //cout << "done with res " << res << endl;

    curMn = (long long)1e18;
    l = r = m - 1;
    getMn(0 , m - 1 , 1 , curMn , curIdx);

    mnVal = (long long)1e18;
    l = r = res;
    getMn(0 , m - 1 , 1 ,mnVal , mnIdx);


    mxVal = (long long)-1e18;
    l = res , r = m - 1;
    getMx(0 , m - 1 , 1 , mxVal , mxIdx);

    //cout << mnIdx << " " << mxIdx << " " << curIdx << " " << mnVal << " " << mxVal << " " << curMn << endl;

    if(mxIdx != mnIdx && mxVal - mnVal >= c){
        return curMn - mxVal + c;
    }
    return curMn - mnVal;
}

vector< int > bruteforce(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
        vector< int > s(n , 0);
        int n = (int)c.size();
        for(int i = 0 ;i < n;i++){
            for(int j = 0 ;j < (int)l.size();j++){
                if(l[j] <= i && r[j] >= i){
                    s[i] += v[j];
                    if(s[i] < 0) s[i] = 0;
                    if(s[i] > c[i]) s[i] = c[i];
                }
            }
        }

        return s;
}


std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
    n = (int)c.size();
    m = (int)l.size() + 1;
    vector< int > s(n , 0);

    for(int i = 0 ;i < n;i++){
        add[i].clear();
        rem[i].clear();
    }

    for(int i = 0 ;i < (int)l.size();i++){
        add[l[i]].push_back(i);
        rem[r[i] + 1].push_back(i);
    }

    build(0 , m - 1 , 1);



    for(int i = 0 ;i < n;i++){
        for(int j = 0 ;j < (int)add[i].size();j++){
            ::l = add[i][j] + 1;
            ::r = m - 1;
            val = v[add[i][j]];
            update(0 , m - 1 , 1);
        }
        for(int j = 0 ;j < (int)rem[i].size();j++){
            ::l = rem[i][j] + 1;
            ::r = m - 1;
            val = -v[rem[i][j]];
            update(0 , m - 1 , 1);
        }


        s[i] = solve(c[i]);
    }
/*
    vector< int > bf = bruteforce(c , l , r , v);

    if(bf != s){
        cout << "bad " << endl;

        cout << "input: " << endl;
        cout << (int)c.size() << endl;
        for(int i = 0 ;i < (int)c.size();i++) cout << c[i] << " ";
        cout << endl;
        cout << (int)l.size() << endl;
        for(int i = 0 ;i < (int)l.size();i++){
            cout << l[i] << " " << r[i] << " " << v[i] << endl;
        }
        cout << "--------------------------" << endl;

        for(int i = 0 ;i < (int)bf.size();i++){
            cout << bf[i] << " ";
        }
        cout << endl;

    }
    */

    return s;
}

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