oj.uz

Submission #680424

# Submission time Handle Problem Language Result Execution time Memory
680424 2023-01-10T19:06:37 Z whqkrtk04 Wall (IOI14_wall) C++14
100 / 100
 1564 ms 141364 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }

class segtree {
    private:
    int n;
    vector<pii> seg, lazy;

    const pii inf = {0, INF};
    pii mer_lazy(pii a, pii b) {
        return {min(b.se, max(a.fi, b.fi)), max(b.fi, min(a.se, b.se))};
    }
    pii mer_seg(pii a, pii b) {
        return {min(a.fi, b.fi), max(a.se, b.se)};
    }
    
    void prop(int i, int s, int e) {
        if(s+1 != e) {
            seg[i<<1] = mer_lazy(seg[i<<1], lazy[i]);
            seg[i<<1|1] = mer_lazy(seg[i<<1|1], lazy[i]);
            lazy[i<<1] = mer_lazy(lazy[i<<1], lazy[i]);
            lazy[i<<1|1] = mer_lazy(lazy[i<<1|1], lazy[i]);
        }
        lazy[i] = inf;
    }

    void update(int i, int s, int e, int l, int r, pii x) {
        prop(i, s, e);
        if(e <= l || r <= s) return;
        if(l <= s && e <= r) {
            seg[i] = mer_lazy(seg[i], x);
            lazy[i] = mer_lazy(lazy[i], x);
        } else {
            update(i<<1, s, s+e>>1, l, r, x);
            update(i<<1|1, s+e>>1, e, l, r, x);
            seg[i] = mer_seg(seg[i<<1], seg[i<<1|1]);
        }
    }

    int query(int i, int s, int e, int j) {
        prop(i, s, e);
        if(s+1 == e) return seg[i].fi;
        int mi = s+e>>1;
        if(j < mi) return query(i<<1, s, mi, j);
        else return query(i<<1|1, mi, e, j);
    }

    public:
    segtree(int n) {
        this->n = n;
        seg = vector<pii>(4*n, {0, 0});
        lazy = vector<pii>(4*n, inf);
    }

    void update(int op, int l, int r, int h) {
        r++, op--;
        if(!op) update(1, 0, n, l, r, {h, INF});
        else update(1, 0, n, l, r, {0, h});
    }

    void query(int height[]) {
        for(int i = 0; i < n; i++) height[i] = query(1, 0, n, i);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segtree S(n);
    for(int i = 0; i < k; i++) S.update(op[i], left[i], right[i], height[i]);
    S.query(finalHeight);
    return;
}

Compilation message

wall.cpp: In member function 'void segtree::update(int, int, int, int, int, pii)':
wall.cpp:49:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             update(i<<1, s, s+e>>1, l, r, x);
      |                             ~^~
wall.cpp:50:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             update(i<<1|1, s+e>>1, e, l, r, x);
      |                            ~^~
wall.cpp: In member function 'int segtree::query(int, int, int, int)':
wall.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mi = s+e>>1;
      |                  ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 11 ms 1056 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 120 ms 8044 KB Output is correct
3 Correct 275 ms 4752 KB Output is correct
4 Correct 848 ms 14840 KB Output is correct
5 Correct 510 ms 14720 KB Output is correct
6 Correct 551 ms 14788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 130 ms 8124 KB Output is correct
9 Correct 275 ms 4692 KB Output is correct
10 Correct 843 ms 14820 KB Output is correct
11 Correct 471 ms 14784 KB Output is correct
12 Correct 475 ms 14904 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 129 ms 8136 KB Output is correct
15 Correct 49 ms 1888 KB Output is correct
16 Correct 834 ms 14812 KB Output is correct
17 Correct 473 ms 14788 KB Output is correct
18 Correct 467 ms 14784 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1060 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 138 ms 8076 KB Output is correct
9 Correct 272 ms 4752 KB Output is correct
10 Correct 836 ms 14784 KB Output is correct
11 Correct 452 ms 14784 KB Output is correct
12 Correct 463 ms 14816 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 125 ms 8104 KB Output is correct
15 Correct 44 ms 1868 KB Output is correct
16 Correct 820 ms 14780 KB Output is correct
17 Correct 460 ms 14796 KB Output is correct
18 Correct 465 ms 14708 KB Output is correct
19 Correct 1531 ms 141196 KB Output is correct
20 Correct 1485 ms 141272 KB Output is correct
21 Correct 1561 ms 141224 KB Output is correct
22 Correct 1500 ms 141196 KB Output is correct
23 Correct 1521 ms 141288 KB Output is correct
24 Correct 1564 ms 141260 KB Output is correct
25 Correct 1498 ms 141208 KB Output is correct
26 Correct 1524 ms 141364 KB Output is correct
27 Correct 1504 ms 141296 KB Output is correct
28 Correct 1490 ms 141200 KB Output is correct
29 Correct 1508 ms 141172 KB Output is correct
30 Correct 1496 ms 141280 KB Output is correct