oj.uz

Submission #893133

# Submission time Handle Problem Language Result Execution time Memory
893133 2023-12-26T14:46:17 Z fanwen Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 11696 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;

    build_block(id_block(l));
    for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
        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) {
            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 4 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 4 ms 348 KB Output is correct
3 Correct 482 ms 1616 KB Output is correct
4 Correct 495 ms 1616 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 344 KB Output is correct
2 Correct 15 ms 348 KB Output is correct
3 Execution timed out 2078 ms 11696 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 8112 KB Output is correct
2 Correct 1728 ms 11524 KB Output is correct
3 Correct 341 ms 3156 KB Output is correct
4 Correct 498 ms 3040 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 4 ms 348 KB Output is correct
3 Correct 482 ms 1616 KB Output is correct
4 Correct 495 ms 1616 KB Output is correct
5 Correct 14 ms 344 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 341 ms 3156 KB Output is correct
8 Correct 498 ms 3040 KB Output is correct
9 Correct 479 ms 3444 KB Output is correct
10 Correct 493 ms 3464 KB Output is correct
11 Correct 479 ms 3416 KB Output is correct
12 Correct 491 ms 3412 KB Output is correct
13 Correct 475 ms 3572 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 4 ms 348 KB Output is correct
3 Correct 482 ms 1616 KB Output is correct
4 Correct 495 ms 1616 KB Output is correct
5 Correct 14 ms 344 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Execution timed out 2078 ms 11696 KB Time limit exceeded
8 Halted 0 ms 0 KB -