oj.uz

Submission #485579

# Submission time Handle Problem Language Result Execution time Memory
485579 2021-11-08T11:06:44 Z Mazaalai Wall (IOI14_wall) C++14
100 / 100
 730 ms 142220 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
const int N1 = 2e6 + 5;
const int M = 4 * N;
struct Node {
    int mini, maxi, lazy;
    Node() {
        mini = maxi = 0;
        lazy = -1;
    }
    void setMinMax(int a, int b) {
        mini = a, maxi = b;
    }
};
vector <int> ans(N1);
vector <int> idx(N1);
vector <Node> node(M);
void propagate(int head) {
    if (node[head].lazy == -1) return;
    int val = node[head].lazy;
    node[head].lazy = -1;
    node[head*2+1].setMinMax(val, val);
    node[head*2+2].setMinMax(val, val);
    node[head*2+1].lazy = val;
    node[head*2+2].lazy = val;
}
void update(int l, int r, int L, int R, int val, bool type, int head) {
    if ((l > R) || 
        (L > r) ||
        (type && node[head].mini >= val) ||
        (!type && node[head].maxi <= val)
    ) return;
    if (L <= l && r <= R && node[head].mini == node[head].maxi) {
        node[head].setMinMax(val, val);
        node[head].lazy = val;
        return;
    }
    propagate(head);

    int mid = (l+r)>>1;
    update(l, mid, L, R, val, type, head*2+1);
    update(mid+1, r, L, R, val, type, head*2+2);
    node[head].setMinMax(
        min(node[head*2+1].mini, node[head*2+2].mini),
        max(node[head*2+1].maxi, node[head*2+2].maxi)
    );

}
void dfs(int l, int r, int head) {
    if (l == r) {
        ans[l] = node[head].mini;
        return;
    }
    propagate(head);
    int mid = (l+r)>>1;
    dfs(l, mid, head*2+1);
    dfs(mid+1, r, head*2+2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    
    // compress left right, 
    for (int i = 0; i < k; i++) {
        idx[left[i]] = idx[right[i]] = 1;
    }
    int curId = 0;
    for (int i = 0; i < n; i++) {
        if (idx[i] == 1) {
            idx[i] = curId++;
            continue;
        }
        int j = i;
        while(j + 1 < n && idx[j+1]==0) j++;
        for (int k = i; k <= j; k++) idx[k] = curId;
        i = j;
        curId++;
    }
    //  update
    for (int i = 0; i < k; i++) {
        // update(0, n-1, idx[left[i]], idx[right[i]], height[i], (op[i]==1?1:0), 0);
        update(0, n-1, left[i], right[i], height[i], (op[i]==1?1:0), 0);
    }
    dfs(0, n-1, 0);
    for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 109764 KB Output is correct
2 Correct 46 ms 109908 KB Output is correct
3 Correct 46 ms 109892 KB Output is correct
4 Correct 52 ms 110008 KB Output is correct
5 Correct 48 ms 110020 KB Output is correct
6 Correct 48 ms 110024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 109868 KB Output is correct
2 Correct 171 ms 117624 KB Output is correct
3 Correct 111 ms 113272 KB Output is correct
4 Correct 202 ms 118232 KB Output is correct
5 Correct 212 ms 118756 KB Output is correct
6 Correct 228 ms 118872 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 109764 KB Output is correct
2 Correct 54 ms 109944 KB Output is correct
3 Correct 54 ms 109836 KB Output is correct
4 Correct 50 ms 110020 KB Output is correct
5 Correct 48 ms 109984 KB Output is correct
6 Correct 48 ms 109988 KB Output is correct
7 Correct 44 ms 109764 KB Output is correct
8 Correct 170 ms 117636 KB Output is correct
9 Correct 110 ms 113184 KB Output is correct
10 Correct 199 ms 118232 KB Output is correct
11 Correct 218 ms 118700 KB Output is correct
12 Correct 239 ms 118744 KB Output is correct
13 Correct 44 ms 109872 KB Output is correct
14 Correct 174 ms 117704 KB Output is correct
15 Correct 78 ms 110504 KB Output is correct
16 Correct 571 ms 118468 KB Output is correct
17 Correct 326 ms 118580 KB Output is correct
18 Correct 321 ms 118492 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 109796 KB Output is correct
2 Correct 47 ms 109892 KB Output is correct
3 Correct 48 ms 109824 KB Output is correct
4 Correct 50 ms 110020 KB Output is correct
5 Correct 49 ms 110020 KB Output is correct
6 Correct 49 ms 110020 KB Output is correct
7 Correct 45 ms 109840 KB Output is correct
8 Correct 170 ms 117624 KB Output is correct
9 Correct 111 ms 113220 KB Output is correct
10 Correct 196 ms 118308 KB Output is correct
11 Correct 208 ms 118724 KB Output is correct
12 Correct 240 ms 118684 KB Output is correct
13 Correct 43 ms 109872 KB Output is correct
14 Correct 173 ms 117700 KB Output is correct
15 Correct 75 ms 110416 KB Output is correct
16 Correct 573 ms 118492 KB Output is correct
17 Correct 320 ms 118468 KB Output is correct
18 Correct 327 ms 118488 KB Output is correct
19 Correct 659 ms 135748 KB Output is correct
20 Correct 678 ms 139588 KB Output is correct
21 Correct 725 ms 141968 KB Output is correct
22 Correct 670 ms 139668 KB Output is correct
23 Correct 676 ms 139432 KB Output is correct
24 Correct 670 ms 139588 KB Output is correct
25 Correct 661 ms 139432 KB Output is correct
26 Correct 684 ms 142220 KB Output is correct
27 Correct 730 ms 142148 KB Output is correct
28 Correct 676 ms 139816 KB Output is correct
29 Correct 665 ms 139648 KB Output is correct
30 Correct 669 ms 139720 KB Output is correct