oj.uz

Submission #882495

# Submission time Handle Problem Language Result Execution time Memory
882495 2023-12-03T09:06:43 Z Desh03 Wall (IOI14_wall) C++17
100 / 100
 681 ms 152740 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 2e9;
 
struct node {
    int mn1;
    int mn2;
    int mx1;
    int mx2;
    int mncnt;
    int mxcnt;
    int sum;
    int lz;
    node() : mn1(INF), mn2(INF), mx1(-INF), mx2(-INF), mncnt(0), mxcnt(0), sum(0), lz(0) { };
};
 
struct SegmentTreeBeats {
    vector<node> st;
    int sz;
    void build(int v, int l, int r, vector<int> &a) {
        if (l == r) {
            st[v].mn1 = a[l];
            st[v].mx1 = a[l];
            st[v].mncnt = st[v].mxcnt = 1;
            st[v].sum = a[l];
            return;
        }
        int m = l + r >> 1;
        build(v << 1, l, m, a);
        build(v << 1 | 1, m + 1, r, a);
        pull(v);
    }
    void applyleaf(int v, int x) {
        st[v].mn1 = x;
        st[v].mx1 = x;
        st[v].mncnt = st[v].mxcnt = 1;
        st[v].sum = x;
    }
    SegmentTreeBeats(const vector<int> &a) : sz(a.size()) {
        while (sz & sz - 1) ++sz;
        st.resize(sz << 1);
        for (int i = 0; i < a.size(); i++) applyleaf(i + sz, a[i]);
        for (int i = sz - 1; i > 0; i--) pull(i);
    }
    SegmentTreeBeats(int n) : sz(n) {
        while (sz & sz - 1) ++sz;
        st.resize(sz << 1);
        for (int i = 0; i < n; i++) {
            applyleaf(i + sz, 0);
        }
        for (int i = sz - 1; i > 0; i--) {
            pull(i);
        }
    }
    void apply1(int v, int x, int l, int r) {
        if (x == 0) return;
        st[v].mx1 += x;
        if (st[v].mx2 != -INF) st[v].mx2 += x;
        st[v].mn1 += x;
        if (st[v].mn2 != INF) st[v].mn2 += x;
        st[v].sum += (r - l + 1) * x;
        st[v].lz += x;
    }
    void apply2(int v, int x, bool f) {
        if (st[v].mn1 >= x) return;
        st[v].sum = st[v].sum - st[v].mncnt * st[v].mn1 + st[v].mncnt * x;
        if (f) {
            st[v].mn1 = st[v].mx1 = x;
        } else {
            st[v].mn1 = x;
            if (x >= st[v].mx1) st[v].mx1 = x;
            else if (x > st[v].mx2) st[v].mx2 = x;
        }
    }
    void apply3(int v, int x, bool f) {
        if (st[v].mx1 <= x) return;
        st[v].sum = st[v].sum - st[v].mxcnt * st[v].mx1 + st[v].mxcnt * x;
        if (f) {
            st[v].mx1 = st[v].mn1 = x;
        } else {
            st[v].mx1 = x;
            if (x <= st[v].mn1) st[v].mn1 = x;
            else if (x < st[v].mn2) st[v].mn2 = x;
        }
    }
    void push(int v, int l, int r) {
        int m = l + r >> 1;
        apply1(v << 1, st[v].lz, l, m);
        apply1(v << 1 | 1, st[v].lz, m + 1, r);
        st[v].lz = 0;
        apply2(v << 1, st[v].mn1, l == m);
        apply2(v << 1 | 1, st[v].mn1, m + 1 == r);
        apply3(v << 1, st[v].mx1, l == m);
        apply3(v << 1 | 1, st[v].mx1, m + 1 == r);
    }
    void pull(int v) {
        st[v].sum = st[v << 1].sum + st[v << 1 | 1].sum;
        if (st[v << 1].mn1 == st[v << 1 | 1].mn1) {
            st[v].mn1 = st[v << 1].mn1;
            st[v].mncnt = st[v << 1].mncnt + st[v << 1 | 1].mncnt;
            st[v].mn2 = min(st[v << 1].mn2, st[v << 1 | 1].mn2);
        } else if (st[v << 1].mn1 > st[v << 1 | 1].mn1) {
            st[v].mn1 = st[v << 1 | 1].mn1;
            st[v].mncnt = st[v << 1 | 1].mncnt;
            st[v].mn2 = min(st[v << 1].mn1, st[v << 1 | 1].mn2);
        } else {
            st[v].mn1 = st[v << 1].mn1;
            st[v].mncnt = st[v << 1].mncnt;
            st[v].mn2 = min(st[v << 1].mn2, st[v << 1 | 1].mn1);
        }
        if (st[v << 1].mx1 == st[v << 1 | 1].mx1) {
            st[v].mx1 = st[v << 1].mx1;
            st[v].mxcnt = st[v << 1].mxcnt + st[v << 1 | 1].mxcnt;
            st[v].mx2 = max(st[v << 1].mx2, st[v << 1 | 1].mx2);
        } else if (st[v << 1].mx1 < st[v << 1 | 1].mx1) {
            st[v].mx1 = st[v << 1 | 1].mx1;
            st[v].mxcnt = st[v << 1 | 1].mxcnt;
            st[v].mx2 = max(st[v << 1].mx1, st[v << 1 | 1].mx2);
        } else {
            st[v].mx1 = st[v << 1].mx1;
            st[v].mxcnt = st[v << 1].mxcnt;
            st[v].mx2 = max(st[v << 1].mx2, st[v << 1 | 1].mx1);
        }
    }
    void upd1(int v, int l, int r, int ql, int qr, int x) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            apply1(v, x, l, r);
            return;
        }
        push(v, l, r);
        int m = l + r >> 1;
        upd1(v << 1, l, m, ql, qr, x);
        upd1(v << 1 | 1, m + 1, r, ql, qr, x);
        pull(v);
    }
    void upd2(int v, int l, int r, int ql, int qr, int x) {
        if (l > qr || r < ql || st[v].mn1 >= x) return;
        if (l >= ql && r <= qr && st[v].mn2 > x) {
            apply2(v, x, l == r);
            return;
        }
        push(v, l, r);
        int m = l + r >> 1;
        upd2(v << 1, l, m, ql, qr, x);
        upd2(v << 1 | 1, m + 1, r, ql, qr, x);
        pull(v);
    }
    void upd3(int v, int l, int r, int ql, int qr, int x) {
        if (l > qr || r < ql || st[v].mx1 <= x) return;
        if (l >= ql && r <= qr && st[v].mx2 < x) {
            apply3(v, x, l == r);
            return;
        }
        push(v, l, r);
        int m = l + r >> 1;
        upd3(v << 1, l, m, ql, qr, x);
        upd3(v << 1 | 1, m + 1, r, ql, qr, x);
        pull(v);
    }
    void pushdown(int v, int l, int r) {
        if (l == r) return;
        push(v, l, r);
        int m = l + r >> 1;
        pushdown(v << 1, l, m);
        pushdown(v << 1 | 1, m + 1, r);
    }
    int qry(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return st[v].sum;
        push(v, l, r);
        int m = l + r >> 1;
        return qry(v << 1, l, m, ql, qr) + qry(v << 1 | 1, m + 1, r, ql, qr);
    }
    void pushdown() {
        pushdown(1, 0, sz - 1);
    }
    void upd1(int l, int r, int x) {
        upd1(1, 0, sz - 1, l, r, x);
    }
    void upd2(int l, int r, int x) {
        upd2(1, 0, sz - 1, l, r, x);
    }
    void upd3(int l, int r, int x) {
        upd3(1, 0, sz - 1, l, r, x);
    }
    int qry(int l, int r) {
        return qry(1, 0, sz - 1, l, r);
    }
    int get(int id) {
        return st[id + sz].mx1;
    }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]) {
    SegmentTreeBeats st(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            st.upd2(left[i], right[i], height[i]);
        } else {
            st.upd3(left[i], right[i], height[i]);
        }
    }
    st.pushdown();
    for (int i = 0; i < n; i++) {
        finalheight[i] = st.get(i);
    }
}

Compilation message

wall.cpp: In member function 'void SegmentTreeBeats::build(int, int, int, std::vector<int>&)':
wall.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In constructor 'SegmentTreeBeats::SegmentTreeBeats(const std::vector<int>&)':
wall.cpp:42:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |         while (sz & sz - 1) ++sz;
      |                     ~~~^~~
wall.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < a.size(); i++) applyleaf(i + sz, a[i]);
      |                         ~~^~~~~~~~~~
wall.cpp: In constructor 'SegmentTreeBeats::SegmentTreeBeats(int)':
wall.cpp:48:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |         while (sz & sz - 1) ++sz;
      |                     ~~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::push(int, int, int)':
wall.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd1(int, int, int, int, int, int)':
wall.cpp:134:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd2(int, int, int, int, int, int)':
wall.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd3(int, int, int, int, int, int)':
wall.cpp:158:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::pushdown(int, int, int)':
wall.cpp:166:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In member function 'int SegmentTreeBeats::qry(int, int, int, int, int)':
wall.cpp:174:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1656 KB Output is correct
5 Correct 5 ms 1660 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 107 ms 11188 KB Output is correct
3 Correct 58 ms 7840 KB Output is correct
4 Correct 134 ms 21844 KB Output is correct
5 Correct 141 ms 22236 KB Output is correct
6 Correct 167 ms 21272 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 107 ms 11088 KB Output is correct
9 Correct 57 ms 7764 KB Output is correct
10 Correct 143 ms 21780 KB Output is correct
11 Correct 159 ms 22028 KB Output is correct
12 Correct 167 ms 21248 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 111 ms 11124 KB Output is correct
15 Correct 34 ms 3676 KB Output is correct
16 Correct 529 ms 21904 KB Output is correct
17 Correct 277 ms 21604 KB Output is correct
18 Correct 275 ms 21596 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 107 ms 11264 KB Output is correct
9 Correct 59 ms 7756 KB Output is correct
10 Correct 139 ms 21876 KB Output is correct
11 Correct 149 ms 22220 KB Output is correct
12 Correct 170 ms 21340 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 110 ms 11200 KB Output is correct
15 Correct 31 ms 3420 KB Output is correct
16 Correct 537 ms 21852 KB Output is correct
17 Correct 271 ms 21592 KB Output is correct
18 Correct 287 ms 21584 KB Output is correct
19 Correct 668 ms 152652 KB Output is correct
20 Correct 630 ms 152660 KB Output is correct
21 Correct 626 ms 152664 KB Output is correct
22 Correct 641 ms 152652 KB Output is correct
23 Correct 616 ms 152740 KB Output is correct
24 Correct 616 ms 152652 KB Output is correct
25 Correct 613 ms 147660 KB Output is correct
26 Correct 620 ms 147640 KB Output is correct
27 Correct 617 ms 147300 KB Output is correct
28 Correct 624 ms 147284 KB Output is correct
29 Correct 681 ms 147284 KB Output is correct
30 Correct 618 ms 147192 KB Output is correct