oj.uz

답안 #498660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498660 2021-12-26T04:45:31 Z model_code Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1539 ms 5064 KB 
// 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 149 ms 1348 KB Output is correct
4 Correct 166 ms 1404 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 1539 ms 5024 KB Output is correct
4 Correct 1306 ms 5064 KB Output is correct
5 Correct 1520 ms 4912 KB Output is correct
6 Correct 1250 ms 4860 KB Output is correct
7 Correct 107 ms 972 KB Output is correct
8 Correct 132 ms 1008 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 972 KB Output is correct
2 Correct 132 ms 1008 KB Output is correct
3 Correct 538 ms 4192 KB Output is correct
4 Correct 681 ms 4228 KB Output is correct

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 149 ms 1348 KB Output is correct
4 Correct 166 ms 1404 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 107 ms 972 KB Output is correct
8 Correct 132 ms 1008 KB Output is correct
9 Correct 141 ms 1288 KB Output is correct
10 Correct 193 ms 1336 KB Output is correct
11 Correct 140 ms 1340 KB Output is correct
12 Correct 156 ms 1384 KB Output is correct
13 Correct 149 ms 1324 KB Output is correct

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 149 ms 1348 KB Output is correct
4 Correct 166 ms 1404 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1539 ms 5024 KB Output is correct
8 Correct 1306 ms 5064 KB Output is correct
9 Correct 1520 ms 4912 KB Output is correct
10 Correct 1250 ms 4860 KB Output is correct
11 Correct 538 ms 4192 KB Output is correct
12 Correct 681 ms 4228 KB Output is correct
13 Correct 141 ms 1288 KB Output is correct
14 Correct 193 ms 1336 KB Output is correct
15 Correct 140 ms 1340 KB Output is correct
16 Correct 156 ms 1384 KB Output is correct
17 Correct 149 ms 1324 KB Output is correct
18 Correct 107 ms 972 KB Output is correct
19 Correct 132 ms 1008 KB Output is correct
20 Correct 966 ms 4092 KB Output is correct
21 Correct 1131 ms 4248 KB Output is correct
22 Correct 943 ms 4144 KB Output is correct
23 Correct 1116 ms 4136 KB Output is correct
24 Correct 989 ms 4152 KB Output is correct