제출 #498660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498660		model_code	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	1539 ms	5064 KiB

weirdtree

// weirdtree_100_sqrt_ruxandra.cpp

#include <bits/stdc++.h>
#include "weirdtree.h"
#define DIMN 300010
using namespace std;

struct bucketinfo{
    long long sum;
    int maxi1, cntmaxi1, maxi2, lazy;
    /// lazy este cea mai mare valoare care poate sa apara ever in subarb
} bucket[600];



int v[DIMN], n , bucksize;

int whichBucket(int i){
    return (i - 1) / bucksize + 1;
}

int startOfBuck (int i){
    return (i - 1) * bucksize + 1;
}

int endOfBuck (int i){
    return startOfBuck(i) + bucksize - 1;
}

bucketinfo query (int l , int r){
    int start, stop, i, val;
    bucketinfo sol = {0 , 0 , 0 , 0 , 0};

    if (whichBucket(l) == whichBucket(r)){
        for (i = l ; i <= r ; i++){
            sol.sum += min(v[i] , bucket[whichBucket(l)].maxi1);
            val = min(v[i] , bucket[whichBucket(l)].maxi1);
            if (sol.maxi1 < val){
                sol.maxi2 = sol.maxi1;
                sol.maxi1 = val;
                sol.cntmaxi1 = 1;
            }
            else if (sol.maxi1 == val){
                sol.cntmaxi1++;
            }
            else if (sol.maxi2 < val){
                sol.maxi2 = val;
            }
        }
        return sol;
    }

    start = (whichBucket(l) != whichBucket(l - 1) || l == 1 ? whichBucket(l) : whichBucket(l) + 1);
    stop = (whichBucket(r) != whichBucket(r + 1) || r == n ? whichBucket(r) : whichBucket(r) - 1);

    //printf ("%d %d %d\n", whichBucket(l), whichBucket(r), bucksize);

    for (i = start ; i <= stop ; i++){
        //printf ("%d    %d %d   %lld\n", i , startOfBuck(i), endOfBuck(i), bucket[i].sum);
        sol.sum += bucket[i].sum;
        if (sol.maxi1 < bucket[i].maxi1){
            sol.maxi2 = sol.maxi1;
            sol.maxi1 = bucket[i].maxi1;
            sol.cntmaxi1 = bucket[i].cntmaxi1;
        }
        else if (sol.maxi1 == bucket[i].maxi1){
            sol.cntmaxi1 += bucket[i].cntmaxi1;
        }
        if (sol.maxi2 < bucket[i].maxi2){
            sol.maxi2 = bucket[i].maxi2;
        }
        if (sol.maxi2 < bucket[i].maxi1 && sol.maxi1 > bucket[i].maxi1){
            sol.maxi2 = bucket[i].maxi1;
        }
    }

    if (start != whichBucket(l)){
        for (i = l ; whichBucket(i) != start; i++){
            sol.sum += min(v[i] , bucket[whichBucket(l)].maxi1);
            val = min(v[i] , bucket[whichBucket(l)].maxi1);
            if (sol.maxi1 < val){
                sol.maxi2 = sol.maxi1;
                sol.maxi1 = val;
                sol.cntmaxi1 = 1;
            }
            else if (sol.maxi1 == val){
                sol.cntmaxi1++;
            }
            else if (sol.maxi2 < val){
                sol.maxi2 = val;
            }
        }
    }

    if (stop != whichBucket(r)){
        for (i = r ; whichBucket(i) != stop ; i--){
            sol.sum += min(v[i] , bucket[whichBucket(r)].maxi1);
            val = min(v[i] , bucket[whichBucket(r)].maxi1);
            if (sol.maxi1 < val){
                sol.maxi2 = sol.maxi1;
                sol.maxi1 = val;
                sol.cntmaxi1 = 1;
            }
            else if (sol.maxi1 == val){
                sol.cntmaxi1++;
            }
            else if (sol.maxi2 < val){
                sol.maxi2 = val;
            }
        }
    }

    return sol;


}

void updatemanually (int i , int &capacity, int maxi, int l , int r){
    long long sum;
    int maxi1, maxi2, cntmaxi1, val;
    sum = 0;
    maxi1 = 0;
    maxi2 = 0;
    cntmaxi1 = 0;
    for (int j = startOfBuck(i) ; j <= endOfBuck(i) ; j++){
        val = min(v[j], bucket[i].maxi1);
        if (l <= j && j <= r && val > maxi - (capacity > 0)){
            val = maxi - (capacity > 0);
            if (capacity)
                capacity--;
        }
        v[j] = val;
        sum += val;
        if (val > maxi1){
            maxi2 = maxi1;
            maxi1 = val;
            cntmaxi1 = 1;
        }
        else if (val == maxi1){
            cntmaxi1++;
        }
        else if (val > maxi2){
            maxi2 = val;
        }
    }

    bucket[i].sum = sum;
    bucket[i].maxi1 = maxi1;
    bucket[i].cntmaxi1 = cntmaxi1;
    bucket[i].maxi2 = maxi2;
    bucket[i].lazy = maxi1;
}

void goOverAndReplace (int l , int r , int capacity, int maxi){
    int i , start , stop;
    start = (whichBucket(l) != whichBucket(l - 1) || l == 1 ? whichBucket(l) : whichBucket(l) + 1);
    stop = (whichBucket(r) != whichBucket(r + 1) || r == n ? whichBucket(r) : whichBucket(r) - 1);

    if (whichBucket(l) == whichBucket(r)){
        updatemanually(whichBucket(l), capacity, maxi, l , r);
        return;
    }

    if (start != whichBucket(l) && bucket[whichBucket(l)].maxi1 > maxi - (capacity > 0)){
        updatemanually(whichBucket(l), capacity, maxi, l , r);
    }

    for (i = start ; i <= stop ; i++){
        if (bucket[i].maxi1 > maxi  - (capacity > 0)){ /// there is something to change
            if ((bucket[i].maxi2 < maxi - (capacity > 0)  || bucket[i].cntmaxi1 == endOfBuck(i) - startOfBuck(i) + 1)
                && (capacity == 0 || capacity > bucket[i].cntmaxi1)){ /// just replace
                bucket[i].sum = bucket[i].sum - 1LL * bucket[i].maxi1 * bucket[i].cntmaxi1
                                              + 1LL * ( maxi - (capacity > 0) ) * bucket[i].cntmaxi1;
                bucket[i].maxi1 = maxi - (capacity > 0);
                bucket[i].lazy = maxi - (capacity > 0);
                if (capacity)
                    capacity -= bucket[i].cntmaxi1;

            }
            else { /// cannot be sure, update manually
                updatemanually(i , capacity, maxi, l , r);

            }
        }
    }

    if (stop != whichBucket(r) && bucket[whichBucket(r)].maxi1 > maxi - (capacity > 0)){
        updatemanually(whichBucket(r), capacity, maxi, l , r);
    }

}

void initialise (int N , int q , int h[]){
    int i, maxi1, maxi2, cntmaxi1;
    long long sum;
    n = N;
    for (i = 1 ; i <= n ; i++){
        v[i] = h[i];
    }
    bucksize = sqrt(n);

    sum = 0;
    maxi1 = 0;
    maxi2 = 0;
    cntmaxi1 = 0;

    for (i = 1 ; i <= n ; i++){
        sum += v[i];
        if (v[i] > maxi1){
            maxi2 = maxi1;
            maxi1 = v[i];
            cntmaxi1 = 1;
        }
        else if (v[i] == maxi1){
            cntmaxi1++;
        }
        else if (v[i] > maxi2){
            maxi2 = v[i];
        }
        if (whichBucket(i) != whichBucket(i + 1) || i == n){
            bucket[whichBucket(i)].sum = sum;
            bucket[whichBucket(i)].maxi1 = maxi1;
            bucket[whichBucket(i)].cntmaxi1 = cntmaxi1;
            bucket[whichBucket(i)].maxi2 = maxi2;
            bucket[whichBucket(i)].lazy = maxi1;
            sum = maxi1 = maxi2 = cntmaxi1 = 0;
        }
    }
}

void cut (int l, int r, int k){
    long long cuts;
    int capacity;
    bucketinfo ans;
    while (k){

        ans = query(l , r);

        if (ans.maxi1 == 0){
            /// not much you can do
            return;
        }

        cuts = 1LL * (ans.maxi1 - ans.maxi2) * ans.cntmaxi1;

        if (cuts <= k){
            /// all values equal to maxi1 become equal to maxi2 in [l , r]
            k -= cuts;
            capacity = 0;
            goOverAndReplace(l , r, 0, ans.maxi2);
        }
        else {
            /// too many values bigger than maxi2, do stuff
            int valueToReach = ans.maxi1 - k / ans.cntmaxi1;
            capacity = k % ans.cntmaxi1;
            goOverAndReplace(l , r , capacity, valueToReach);
            k = 0;
        }

    }
}

void magic (int poz, int k){
    int i, maxi1, maxi2, cntmaxi1, start , stop, val;
    long long sum;
    start = startOfBuck(whichBucket(poz));
    stop = endOfBuck(whichBucket(poz));
    sum = 0;
    maxi1 = 0;
    maxi2 = 0;
    cntmaxi1 = 0;

    for (i = start ; i <= stop ; i++){
        if (i == poz){
            val = k;
        }
        else {
            val = min(v[i], bucket[whichBucket(poz)].maxi1);
        }
        v[i] = val;
        sum += val;
        if (val > maxi1){
            maxi2 = maxi1;
            maxi1 = val;
            cntmaxi1 = 1;
        }
        else if (val == maxi1){
            cntmaxi1++;
        }
        else if (val > maxi2){
            maxi2 = val;
        }
    }

    bucket[whichBucket(poz)].sum = sum;
    bucket[whichBucket(poz)].maxi1 = maxi1;
    bucket[whichBucket(poz)].cntmaxi1 = cntmaxi1;
    bucket[whichBucket(poz)].maxi2 = maxi2;
    bucket[whichBucket(poz)].lazy = maxi1;
}

long long inspect (int l, int r){
    return query(l , r).sum;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29