oj.uz

Submission #700251

# Submission time Handle Problem Language Result Execution time Memory
700251 2023-02-19T03:58:09 Z boyliguanhan Wall (IOI14_wall) C++17
100 / 100
 941 ms 118848 KB 
#include <iostream>
#include<algorithm>
#define M 0xfffff
#include "wall.h"
using namespace std;
struct seg {
    int v, l, r, lzmn, lzmx;
} t[8000100];
void build(int i, int l, int r) {
    t[i] = { 0, l, r, M, 0 };
    if (l ^ r)
        build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
}
void cmn(int i, int v) {
    t[i].lzmn = min(t[i].lzmn, v);
    t[i].lzmx = min(t[i].lzmx, v);
}
void cmx(int i, int v) {
    t[i].lzmn = max(t[i].lzmn, v);
    t[i].lzmx = max(t[i].lzmx, v);
}
void pd(int i) {
    if (t[i].lzmn != M) {
        if (t[i].l != t[i].r)
            cmn(i * 2, t[i].lzmn), cmn(i * 2 + 1, t[i].lzmn);
        else
            t[i].v = min(t[i].v, t[i].lzmn);
        t[i].lzmn = M;
    }
    if (t[i].lzmx) {
        if (t[i].l != t[i].r)
            cmx(i * 2, t[i].lzmx), cmx(i * 2 + 1, t[i].lzmx);
        else
            t[i].v = max(t[i].v, t[i].lzmx);
        t[i].lzmx = 0;
    }
}
void umn(int i, int l, int r, int v) {
    if (l <= t[i].l && t[i].r <= r) {
        cmn(i, v);
        return;
    }
    pd(i);
    if (t[i * 2].r < r)
        umn(i * 2 + 1, l, r, v);
    if (l <= t[i * 2].r)
        umn(i * 2, l, r, v);
}
void umx(int i, int l, int r, int v) {
    if (l <= t[i].l && t[i].r <= r) {
        cmx(i, v);
        return;
    }
    pd(i);
    if (t[i * 2].r < r)
        umx(i * 2 + 1, l, r, v);
    if (l <= t[i * 2].r)
        umx(i * 2, l, r, v);
}
int query(int i, int x) {
    pd(i);
    if (t[i].l == t[i].r)
        return t[i].v;
    if (t[i * 2].r < x)
        return query(i * 2 + 1, x);
    return query(i * 2, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1, 0, n-1);
    for (int i = 0; i < k; i++) {
        (op[i]==1?umx:umn)(1, left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; i++)
        finalHeight[i] = query(1, i);
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:13:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
      |                         ~~^~~
wall.cpp:13:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
      |                                                       ~~~~~~^~~

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 384 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1060 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 143 ms 8052 KB Output is correct
3 Correct 172 ms 4896 KB Output is correct
4 Correct 439 ms 13784 KB Output is correct
5 Correct 268 ms 14340 KB Output is correct
6 Correct 249 ms 14292 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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1064 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 159 ms 8080 KB Output is correct
9 Correct 150 ms 4900 KB Output is correct
10 Correct 443 ms 13780 KB Output is correct
11 Correct 304 ms 14264 KB Output is correct
12 Correct 273 ms 14296 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 142 ms 8136 KB Output is correct
15 Correct 35 ms 2208 KB Output is correct
16 Correct 490 ms 14016 KB Output is correct
17 Correct 273 ms 14028 KB Output is correct
18 Correct 252 ms 14060 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 1108 KB Output is correct
5 Correct 5 ms 1068 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 150 ms 8088 KB Output is correct
9 Correct 168 ms 4892 KB Output is correct
10 Correct 477 ms 13780 KB Output is correct
11 Correct 293 ms 14296 KB Output is correct
12 Correct 249 ms 14292 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 151 ms 8104 KB Output is correct
15 Correct 30 ms 2220 KB Output is correct
16 Correct 488 ms 14028 KB Output is correct
17 Correct 254 ms 14036 KB Output is correct
18 Correct 262 ms 14044 KB Output is correct
19 Correct 838 ms 108360 KB Output is correct
20 Correct 858 ms 116320 KB Output is correct
21 Correct 941 ms 118748 KB Output is correct
22 Correct 886 ms 116240 KB Output is correct
23 Correct 816 ms 116188 KB Output is correct
24 Correct 918 ms 116248 KB Output is correct
25 Correct 853 ms 116296 KB Output is correct
26 Correct 936 ms 118772 KB Output is correct
27 Correct 908 ms 118848 KB Output is correct
28 Correct 863 ms 116280 KB Output is correct
29 Correct 870 ms 116332 KB Output is correct
30 Correct 845 ms 116236 KB Output is correct