oj.uz

Submission #893134

# Submission time Handle Problem Language Result Execution time Memory
893134 2023-12-26T14:47:53 Z fanwen Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 5832 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 {
                    build_block(i);
                    for (int j = begin_block(i); j <= end_block(i) && k > 0; ++j) {
                        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 516 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 516 KB Output is correct
3 Correct 410 ms 1424 KB Output is correct
4 Correct 416 ms 1408 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 10 ms 348 KB Output is correct
3 Execution timed out 2052 ms 5832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 4192 KB Output is correct
2 Correct 1406 ms 4440 KB Output is correct
3 Correct 255 ms 1140 KB Output is correct
4 Correct 453 ms 1140 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 516 KB Output is correct
3 Correct 410 ms 1424 KB Output is correct
4 Correct 416 ms 1408 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 255 ms 1140 KB Output is correct
8 Correct 453 ms 1140 KB Output is correct
9 Correct 405 ms 1404 KB Output is correct
10 Correct 423 ms 1632 KB Output is correct
11 Correct 406 ms 1468 KB Output is correct
12 Correct 412 ms 1428 KB Output is correct
13 Correct 400 ms 1616 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 516 KB Output is correct
3 Correct 410 ms 1424 KB Output is correct
4 Correct 416 ms 1408 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Execution timed out 2052 ms 5832 KB Time limit exceeded
8 Halted 0 ms 0 KB -