oj.uz

Submission #435368

# Submission time Handle Problem Language Result Execution time Memory
435368 2021-06-23T09:13:03 Z mohammad_kilani Distributing Candies (IOI21_candies) C++17
100 / 100
 4080 ms 46840 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){
    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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28364 KB Output is correct
2 Correct 15 ms 28464 KB Output is correct
3 Correct 17 ms 28492 KB Output is correct
4 Correct 18 ms 28600 KB Output is correct
5 Correct 28 ms 28620 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2948 ms 46832 KB Output is correct
2 Correct 3006 ms 46840 KB Output is correct
3 Correct 2896 ms 46816 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28492 KB Output is correct
2 Correct 517 ms 40152 KB Output is correct
3 Correct 917 ms 32168 KB Output is correct
4 Correct 3421 ms 46820 KB Output is correct
5 Correct 3544 ms 46820 KB Output is correct
6 Correct 3288 ms 46824 KB Output is correct
7 Correct 1164 ms 46816 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28364 KB Output is correct
2 Correct 16 ms 28376 KB Output is correct
3 Correct 180 ms 38936 KB Output is correct
4 Correct 1089 ms 31048 KB Output is correct
5 Correct 2697 ms 41432 KB Output is correct
6 Correct 2714 ms 41440 KB Output is correct
7 Correct 2565 ms 41436 KB Output is correct
8 Correct 2833 ms 41440 KB Output is correct
9 Correct 2381 ms 41440 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28364 KB Output is correct
2 Correct 15 ms 28464 KB Output is correct
3 Correct 17 ms 28492 KB Output is correct
4 Correct 18 ms 28600 KB Output is correct
5 Correct 28 ms 28620 KB Output is correct
6 Correct 2948 ms 46832 KB Output is correct
7 Correct 3006 ms 46840 KB Output is correct
8 Correct 2896 ms 46816 KB Output is correct
9 Correct 15 ms 28492 KB Output is correct
10 Correct 517 ms 40152 KB Output is correct
11 Correct 917 ms 32168 KB Output is correct
12 Correct 3421 ms 46820 KB Output is correct
13 Correct 3544 ms 46820 KB Output is correct
14 Correct 3288 ms 46824 KB Output is correct
15 Correct 1164 ms 46816 KB Output is correct
16 Correct 16 ms 28364 KB Output is correct
17 Correct 16 ms 28376 KB Output is correct
18 Correct 180 ms 38936 KB Output is correct
19 Correct 1089 ms 31048 KB Output is correct
20 Correct 2697 ms 41432 KB Output is correct
21 Correct 2714 ms 41440 KB Output is correct
22 Correct 2565 ms 41436 KB Output is correct
23 Correct 2833 ms 41440 KB Output is correct
24 Correct 2381 ms 41440 KB Output is correct
25 Correct 15 ms 28364 KB Output is correct
26 Correct 895 ms 31032 KB Output is correct
27 Correct 556 ms 40180 KB Output is correct
28 Correct 3771 ms 46828 KB Output is correct
29 Correct 3493 ms 46796 KB Output is correct
30 Correct 3603 ms 46816 KB Output is correct
31 Correct 4080 ms 46820 KB Output is correct
32 Correct 3921 ms 46832 KB Output is correct