oj.uz

Submission #1007596

# Submission time Handle Problem Language Result Execution time Memory
1007596 2024-06-25T08:39:46 Z Ausp3x Wall (IOI14_wall) C++17
100 / 100
 832 ms 224592 KB 
// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
typedef long long             lng;
typedef unsigned int          uint;
typedef unsigned long long    ulng;
using namespace std;
using namespace __gnu_pbds;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

struct SegTree {
    int mn, mx;
    int l, r;
    SegTree *l_child, *r_child;
    
    SegTree(int l, int r) {
        if (l == r)
            this->mn = this->mx = 0;
        else {
            this->mn = -INF32;
            this->mx = INF32;
        }
        this->l = l;
        this->r = r;

        if (l == r) {
            this->l_child = this->r_child = nullptr;
        } else {
            int m = (l + r) / 2;
            this->l_child = new SegTree(l, m);
            this->r_child = new SegTree(m + 1, r);
        }

        return;
    }

    void push() {
        if (l_child != nullptr && r_child != nullptr) {
            if (this->mn > l_child->mx)
                l_child->mn = l_child->mx = this->mn;
            else if (this->mx < l_child->mn)
                l_child->mn = l_child->mx = this->mx;
            else {
                l_child->mn = max(l_child->mn, this->mn);
                l_child->mx = min(l_child->mx, this->mx);
            }

            if (this->mn > r_child->mx)
                r_child->mn = r_child->mx = this->mn;
            else if (this->mx < r_child->mn)
                r_child->mn = r_child->mx = this->mx;
            else {
                r_child->mn = max(r_child->mn, this->mn);
                r_child->mx = min(r_child->mx, this->mx);
            }
        }
        this->mn = -INF32;
        this->mx = INF32;

        return;
    }

    void rangeMaximize(int L, int R, int h) {
        if (r < L || R < l)
            return;
        else if (L <= l && r <= R) {
            this->mn = max(this->mn, h);
            this->mx = max(this->mx, h);
        } else {
            push();
            l_child->rangeMaximize(L, R, h);
            r_child->rangeMaximize(L, R, h);
        }
    }

    void rangeMinimize(int L, int R, int h) {
        if (r < L || R < l)
            return;
        else if (L <= l && r <= R) {
            this->mn = min(this->mn, h);
            this->mx = min(this->mx, h);
        } else {
            push();
            l_child->rangeMinimize(L, R, h);
            r_child->rangeMinimize(L, R, h);
        }
    }

    int query(int M) {
        if (r < M || M < l)
            return -1;
        else if (l == M && r == M)
            return this->mn;
        else {
            push();
            int lq = l_child->query(M), rq = r_child->query(M);
            if (lq != -1)
                return lq;
            else if (rq != -1)
                return rq;
            else
                return -1;
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegTree *root = new SegTree(0, n - 1);
    
    for (int i = 0; i < k; i++)
        if (op[i] == 1)
            root->rangeMaximize(left[i], right[i], height[i]);
        else if (op[i] == 2)
            root->rangeMinimize(left[i], right[i], height[i]);

    for (int i = 0; i < n; i++)
        finalHeight[i] = root->query(i);

    return;
}

/*
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int op[k], left[k], right[k], height[k], finalHeight[n];
        for (int i = 0; i < k; i++)
            cin >> op[i] >> left[i] >> right[i] >> height[i];

        buildWall(n, k, op, left, right, height, finalHeight);

        for (int i = 0; i < n; i++)
            cout << finalHeight[i] << ' ';
        cout << endl;
    }

    return 0;
}
//*/

Compilation message

wall.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
wall.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
wall.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
wall.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
wall.cpp:21:25: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   21 |     SegTree(int l, int r) {
      |                         ^
wall.cpp:21:25: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:21:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:21:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wall.cpp:42:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   42 |     void push() {
      |               ^
wall.cpp:42:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:42:15: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:42:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wall.cpp:68:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   68 |     void rangeMaximize(int L, int R, int h) {
      |                                           ^
wall.cpp:68:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:68:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:68:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wall.cpp:81:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   81 |     void rangeMinimize(int L, int R, int h) {
      |                                           ^
wall.cpp:81:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:81:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:81:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wall.cpp:94:20: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   94 |     int query(int M) {
      |                    ^
wall.cpp:94:20: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:94:20: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:94:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wall.cpp:112:96: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  112 | void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
      |                                                                                                ^
wall.cpp:112:96: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wall.cpp:112:96: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wall.cpp:112:96: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

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 568 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1576 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 86 ms 11140 KB Output is correct
3 Correct 118 ms 7508 KB Output is correct
4 Correct 339 ms 27696 KB Output is correct
5 Correct 196 ms 28752 KB Output is correct
6 Correct 187 ms 27300 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 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 4 ms 1580 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 13916 KB Output is correct
9 Correct 114 ms 9040 KB Output is correct
10 Correct 316 ms 27728 KB Output is correct
11 Correct 177 ms 28756 KB Output is correct
12 Correct 173 ms 27380 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 77 ms 13936 KB Output is correct
15 Correct 23 ms 3108 KB Output is correct
16 Correct 369 ms 27916 KB Output is correct
17 Correct 209 ms 27384 KB Output is correct
18 Correct 199 ms 27476 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1616 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 4 ms 1580 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 95 ms 13992 KB Output is correct
9 Correct 115 ms 9268 KB Output is correct
10 Correct 338 ms 27732 KB Output is correct
11 Correct 203 ms 28760 KB Output is correct
12 Correct 165 ms 27092 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 78 ms 13904 KB Output is correct
15 Correct 23 ms 3156 KB Output is correct
16 Correct 389 ms 27908 KB Output is correct
17 Correct 197 ms 27336 KB Output is correct
18 Correct 207 ms 27480 KB Output is correct
19 Correct 754 ms 224488 KB Output is correct
20 Correct 746 ms 222060 KB Output is correct
21 Correct 832 ms 224592 KB Output is correct
22 Correct 793 ms 222032 KB Output is correct
23 Correct 782 ms 222104 KB Output is correct
24 Correct 756 ms 222024 KB Output is correct
25 Correct 763 ms 222032 KB Output is correct
26 Correct 805 ms 224488 KB Output is correct
27 Correct 769 ms 224472 KB Output is correct
28 Correct 746 ms 222304 KB Output is correct
29 Correct 769 ms 222036 KB Output is correct
30 Correct 783 ms 222036 KB Output is correct