oj.uz

Submission #893135

# Submission time Handle Problem Language Result Execution time Memory
893135 2023-12-26T14:48:45 Z fanwen Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 5208 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)) {
        build_block(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 4 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 417 ms 1556 KB Output is correct
4 Correct 412 ms 1356 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 11 ms 512 KB Output is correct
3 Execution timed out 2017 ms 5208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 4136 KB Output is correct
2 Correct 1384 ms 4540 KB Output is correct
3 Correct 255 ms 1116 KB Output is correct
4 Correct 391 ms 1112 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 417 ms 1556 KB Output is correct
4 Correct 412 ms 1356 KB Output is correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 11 ms 512 KB Output is correct
7 Correct 255 ms 1116 KB Output is correct
8 Correct 391 ms 1112 KB Output is correct
9 Correct 419 ms 1360 KB Output is correct
10 Correct 413 ms 1688 KB Output is correct
11 Correct 404 ms 1472 KB Output is correct
12 Correct 411 ms 1564 KB Output is correct
13 Correct 397 ms 1360 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 417 ms 1556 KB Output is correct
4 Correct 412 ms 1356 KB Output is correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 11 ms 512 KB Output is correct
7 Execution timed out 2017 ms 5208 KB Time limit exceeded
8 Halted 0 ms 0 KB -