Submission #435273

# Submission time Handle Problem Language Result Execution time Memory
435273 2021-06-23T06:47:08 Z mohammad_kilani Distributing Candies (IOI21_candies) C++17
0 / 100
248 ms 86604 KB
#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){
    if(s == e){
        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){
     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){
    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){
    fix(s , e , idx);
    if(s > r || e < l)
        return false;
    if(s >= l && e <= r){
        if(seg[idx].mn >= val) return false;
        if(s == e){
            mnVal = seg[idx].mn;
            mnIdx = seg[idx].mnIdx;
            return true;
        }
        if(seg[(idx << 1) + 1].mn < val)
            return getFirstMn(((s+e) >> 1) , e , (idx << 1) + 1 , mnVal , mnIdx , val);
        return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);

    }
    if(getFirstMn(((s+e) >> 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 << "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;
        l = mid , r = m - 1;
        curMn = (long long)1e18;
        getMn(0 , m - 1 , 1 , curMn , curIdx);
        l = mnIdx , r = curIdx;
        getFirstMn(0 , m - 1 , 1,  curMn , curIdx , curMn);
        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;
}


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 < (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]);
    }
    return s;
}
# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 57540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 86604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 57752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 57552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 57540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -