oj.uz

Submission #727187

# Submission time Handle Problem Language Result Execution time Memory
727187 2023-04-20T07:34:47 Z hoainiem Wall (IOI14_wall) C++14
100 / 100
 793 ms 186184 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc id<<1
#define rc id<<1^1
#define nmax 2000008
const int inf = 1e6;
using namespace std;
typedef pair<int, int> pii;
pii operator+(pii x, int y){
    return (x.fi < y) ? make_pair(y, x.fi) : ((x.fi > y && y > x.se) ? make_pair(x.fi, y) : x);
}
pii operator-(pii x, int y){
    return (x.fi > y) ? make_pair(y, x.fi) : ((x.fi < y && y < x.se) ? make_pair(x.fi, y) : x);
}
pii operator+(pii x, pii y){
    return (x + y.fi) + y.se;
}
pii operator-(pii x, pii y){
    return (x - y.fi) - y.se;
}
int N, ans[nmax];
struct segmenttrebeats{
    pii mi[nmax << 2], ma[nmax << 2];
    int lazi[nmax << 2];
    void build(int id = 1, int l = 0, int r = N - 1){
        lazi[id] = -1;
        if (l == r){
            mi[id] = {0, inf};
            ma[id] = {0, -inf};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void down(int id){
        mi[lc] = mi[rc] = {lazi[id], inf};
        ma[lc] = ma[rc] = {lazi[id], -inf};
        lazi[lc] = lazi[rc] = lazi[id];
        lazi[id] = -1;
        return;
    }
    void upd_max(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || mi[id].fi >= k)
            return;
        if ((u <= l && r <= v) && (ma[id].fi <= k || mi[id].se == inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_max(u, v, k, lc, l, mid);
        upd_max(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void upd_min(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || k >= ma[id].fi)
            return;
        if ((u <= l && r <= v) && (mi[id].fi >= k || ma[id].se == -inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_min(u, v, k, lc, l, mid);
        upd_min(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void dfs(int id = 1, int l = 0, int r = N - 1){
        if (l == r){
            ans[l] = mi[id].fi;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
}tree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    tree.build();
    for (int i = 0; i < k; i++){
        if (op[i] == 1)
            tree.upd_max(left[i], right[i], height[i]);
        else
            tree.upd_min(left[i], right[i], height[i]);
    }
    tree.dfs();
    for (int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 125480 KB Output is correct
2 Correct 46 ms 125536 KB Output is correct
3 Correct 47 ms 125504 KB Output is correct
4 Correct 51 ms 125940 KB Output is correct
5 Correct 51 ms 125956 KB Output is correct
6 Correct 54 ms 125976 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125448 KB Output is correct
2 Correct 163 ms 133376 KB Output is correct
3 Correct 108 ms 129140 KB Output is correct
4 Correct 201 ms 144884 KB Output is correct
5 Correct 226 ms 145960 KB Output is correct
6 Correct 249 ms 144372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 125516 KB Output is correct
2 Correct 48 ms 125620 KB Output is correct
3 Correct 49 ms 125564 KB Output is correct
4 Correct 52 ms 125916 KB Output is correct
5 Correct 49 ms 125924 KB Output is correct
6 Correct 53 ms 125884 KB Output is correct
7 Correct 50 ms 125420 KB Output is correct
8 Correct 188 ms 139188 KB Output is correct
9 Correct 110 ms 132988 KB Output is correct
10 Correct 262 ms 144928 KB Output is correct
11 Correct 227 ms 145972 KB Output is correct
12 Correct 236 ms 144512 KB Output is correct
13 Correct 51 ms 125516 KB Output is correct
14 Correct 181 ms 139328 KB Output is correct
15 Correct 75 ms 127152 KB Output is correct
16 Correct 513 ms 145224 KB Output is correct
17 Correct 325 ms 144588 KB Output is correct
18 Correct 332 ms 144640 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 125496 KB Output is correct
2 Correct 49 ms 125536 KB Output is correct
3 Correct 70 ms 125512 KB Output is correct
4 Correct 73 ms 125928 KB Output is correct
5 Correct 65 ms 125924 KB Output is correct
6 Correct 67 ms 125892 KB Output is correct
7 Correct 62 ms 125456 KB Output is correct
8 Correct 200 ms 139264 KB Output is correct
9 Correct 141 ms 132924 KB Output is correct
10 Correct 207 ms 144972 KB Output is correct
11 Correct 217 ms 146024 KB Output is correct
12 Correct 240 ms 144460 KB Output is correct
13 Correct 49 ms 125440 KB Output is correct
14 Correct 182 ms 139188 KB Output is correct
15 Correct 89 ms 126988 KB Output is correct
16 Correct 573 ms 145220 KB Output is correct
17 Correct 374 ms 144592 KB Output is correct
18 Correct 336 ms 144644 KB Output is correct
19 Correct 730 ms 186136 KB Output is correct
20 Correct 750 ms 183604 KB Output is correct
21 Correct 793 ms 186156 KB Output is correct
22 Correct 752 ms 183588 KB Output is correct
23 Correct 723 ms 183628 KB Output is correct
24 Correct 763 ms 183568 KB Output is correct
25 Correct 738 ms 183660 KB Output is correct
26 Correct 748 ms 186112 KB Output is correct
27 Correct 761 ms 186184 KB Output is correct
28 Correct 775 ms 183640 KB Output is correct
29 Correct 758 ms 183660 KB Output is correct
30 Correct 729 ms 183800 KB Output is correct