oj.uz

Submission #893136

# Submission time Handle Problem Language Result Execution time Memory
893136 2023-12-26T14:49:27 Z fanwen Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1561 ms 12864 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
 
const int MAX = 3e5 + 5;
const int BLOCK = sqrt(MAX);
const int INF = 1e9 + 1;
 
struct node {
    long long sum;
    int ma1, ma2, fr, lazy;
    node(long long sum = 0, int ma1 = 0, int ma2 = 0, int fr = 0, int lazy = INF) : sum(sum), ma1(ma1), ma2(ma2), fr(fr), lazy(lazy) {}
} infor[600 + 5] ;
 
int n, h[MAX];
 
int id_block(int pos) {
    return (pos) / BLOCK;
}
 
int begin_block(int id) {
    return id * BLOCK;
}
 
int end_block(int id) {
    return min((id + 1) * BLOCK, n) - 1;
}
 
void build_block(int id) {
    int l = begin_block(id), r = end_block(id);
    infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0;
    for (int i = l; i <= r; ++i) {
        h[i] = min(h[i], infor[id].lazy);
        infor[id].sum += h[i];
        if(infor[id].ma1 < h[i]) {
            infor[id].ma2 = infor[id].ma1;
            infor[id].ma1 = h[i];
            infor[id].fr = 1;
        } else {
            if(h[i] == infor[id].ma1) infor[id].fr++;
            else infor[id].ma2 = max(infor[id].ma2, h[i]);
        }
    }
    infor[id].lazy = INF;
}
 
void initialise(int _n, int q, int _h[]) {
    n = _n;
    for (int i = 0; i < n; ++i) h[i] = _h[i + 1];
    for (int i = 0; i < n; i += BLOCK) {
        build_block(i / BLOCK);
    }
}
 
node get(int l, int r) {
    node res;

    for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
        h[i] = min(h[i], infor[id_block(l)].lazy);
        if(res.ma1 < h[i]) {
            res.ma2 = res.ma1;
            res.ma1 = h[i];
            res.fr = 1;
        } else {
            if(res.ma1 == h[i]) res.fr++;
            else res.ma2 = max(res.ma2, h[i]);
        }
        res.sum += h[i];
    }
 
    if(id_block(l) != id_block(r)) {
        for (int i = begin_block(id_block(r)); i <= r; ++i) {
            h[i] = min(h[i], infor[id_block(r)].lazy);
            if(res.ma1 < h[i]) {
                res.ma2 = res.ma1;
                res.ma1 = h[i];
                res.fr = 1;
            } else {
                if(res.ma1 == h[i]) res.fr++;
                else res.ma2 = max(res.ma2, h[i]);
            }
            res.sum += h[i];
        }
    }
 
    for (int i = id_block(l) + 1; i < id_block(r); ++i) {
        if(res.ma1 < infor[i].ma1) {
            res.ma2 = res.ma1;
            res.ma1 = infor[i].ma1;
            res.fr = infor[i].fr;
        } else {
            if(res.ma1 == infor[i].ma1) res.fr += infor[i].fr;
            else res.ma2 = max(res.ma2, infor[i].ma1);
        }
        res.sum += infor[i].sum;
        if(res.ma2 < infor[i].ma2) res.ma2 = infor[i].ma2;
    }
    return res;
}
 
void cut(int l, int r, int k) {
    l--, r--;
    while(k > 0) {
        node res = get(l, r);
        if(res.ma1 == 0) break;
        long long tmp = 1LL * res.fr * (res.ma1 - res.ma2);
        if(k >= tmp) {
            k -= tmp;
            for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
                h[i] = min(h[i], res.ma2);
            }
            build_block(id_block(l));
 
            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r; ++i) {
                    h[i] = min(h[i], res.ma2);
                }
                build_block(id_block(r));
            }
 
            for (int i = id_block(l) + 1; i < id_block(r); ++i) {
                if(infor[i].ma1 == res.ma1) {
                    infor[i].lazy = res.ma2;
                    infor[i].ma1 = res.ma2;
                    infor[i].sum -= 1LL * infor[i].fr * (res.ma1 - res.ma2);
                }
 
                if(infor[i].ma1 == infor[i].ma2) build_block(i);
            }
        } else {
            int rem = k / res.fr;
            for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
                if(h[i] == res.ma1) h[i] -= rem;
            }

            build_block(id_block(l));
            for (int i = id_block(l) + 1; i < id_block(r); ++i) {
                if(infor[i].ma1 == res.ma1) {
                    infor[i].ma1 -= rem;
                    infor[i].lazy = infor[i].ma1;
                    infor[i].sum -= 1LL * infor[i].fr * rem;
                }
            }
            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r; ++i) {
                    if(h[i] == res.ma1) h[i] -= rem;
                }
                build_block(id_block(r));
            }
            k = k - res.fr * rem;
            res.ma1 -= rem;
            assert(k < res.fr);
            for (int i = l; i <= end_block(id_block(l)) && k > 0; ++i) {
                if(h[i] == res.ma1) {
                    h[i]--;
                    k--;
                }
            } 
            build_block(id_block(l));
            for (int i = id_block(l) + 1; i < id_block(r) && k > 0; ++i) {
                if(infor[i].ma1 != res.ma1) continue;
                if(infor[i].fr <= k) {
                    k -= infor[i].fr;
                    infor[i].lazy = --infor[i].ma1;
                    infor[i].sum -= infor[i].fr;    
                    if(infor[i].ma1 == infor[i].ma2) build_block(i);
                } else {
                    for (int j = begin_block(i); j <= end_block(i) && k > 0; ++j) {
                        h[j] = min(h[j], infor[i].lazy);
                        if(h[j] == res.ma1) h[j]--, k--;
                    }
                    build_block(i);
                    break;
                }
            }

            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r && k > 0; ++i) {
                    if(h[i] == res.ma1) h[i]--, k--;
                }
                build_block(id_block(r));
            }
            assert(k <= 0);
        }
    }
}
 
void magic(int i, int x) {
    i--;
    build_block(id_block(i));
    h[i] = x;
    build_block(id_block(i));
}
 
long long inspect(int l, int r) {
    return get(l - 1, r - 1).sum;
}
 
#ifdef LOCAL
 
#include <iostream>
 
using namespace std;
 
int main() {
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
    int N, Q;
    cin >> N >> Q;
 
    int h[N + 1];
 
    for (int i = 1; i <= N; ++i) cin >> h[i];
 
    initialise(N, Q, h);
 
    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;
 
        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if (t == 2) {
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
    return 0;
}
 
#endif // LOCAL
 
// Dream it. Wish it. Do it.

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 321 ms 1364 KB Output is correct
4 Correct 327 ms 1364 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 1556 ms 4936 KB Output is correct
4 Correct 1365 ms 12864 KB Output is correct
5 Correct 1561 ms 12552 KB Output is correct
6 Correct 1378 ms 12676 KB Output is correct
7 Correct 255 ms 1140 KB Output is correct
8 Correct 406 ms 1364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 1140 KB Output is correct
2 Correct 406 ms 1364 KB Output is correct
3 Correct 1153 ms 4144 KB Output is correct
4 Correct 1316 ms 4372 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 321 ms 1364 KB Output is correct
4 Correct 327 ms 1364 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 255 ms 1140 KB Output is correct
8 Correct 406 ms 1364 KB Output is correct
9 Correct 323 ms 1364 KB Output is correct
10 Correct 331 ms 1480 KB Output is correct
11 Correct 324 ms 1360 KB Output is correct
12 Correct 347 ms 1364 KB Output is correct
13 Correct 313 ms 1364 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 321 ms 1364 KB Output is correct
4 Correct 327 ms 1364 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 1556 ms 4936 KB Output is correct
8 Correct 1365 ms 12864 KB Output is correct
9 Correct 1561 ms 12552 KB Output is correct
10 Correct 1378 ms 12676 KB Output is correct
11 Correct 1153 ms 4144 KB Output is correct
12 Correct 1316 ms 4372 KB Output is correct
13 Correct 323 ms 1364 KB Output is correct
14 Correct 331 ms 1480 KB Output is correct
15 Correct 324 ms 1360 KB Output is correct
16 Correct 347 ms 1364 KB Output is correct
17 Correct 313 ms 1364 KB Output is correct
18 Correct 255 ms 1140 KB Output is correct
19 Correct 406 ms 1364 KB Output is correct
20 Correct 1240 ms 11972 KB Output is correct
21 Correct 1344 ms 12296 KB Output is correct
22 Correct 1228 ms 12036 KB Output is correct
23 Correct 1338 ms 12184 KB Output is correct
24 Correct 1258 ms 12028 KB Output is correct